#P2479. 航班
航班
问题描述
有 座城市。还有连接不同城市的单程直飞航班。
直飞航班的可用性由 个长度为 的字符串 表示。如果 的 个字符是 Y
,则有从城市 到城市 的直飞航班;如果是 N
,则没有。
每个城市都出售纪念品;城市 出售价值 的纪念品。
拓拓目前在城市 ,想去城市 (与城市 不同)。(与城市 不同)。 他每次去一个城市(包括 和 ),都会在那里买一件纪念品。
如果从城市 到城市 有多条路线,拓拓决定路线如下:
-
他试图尽量减少从城市 到城市 的航线中直飞航班的数量。
-
然后,他试图使购买的纪念品总价值最大。
确定他是否可以乘坐直飞航班从城市 前往城市 。如果可以,求满足上述条件的路线中的 "直飞航班数 "和 "纪念品总价值"。
给你 对 不同的城市。
当 和 时,请为每个 输出上述问题的答案。
输入格式
第一行一个整数 。
第二行 个整数,。
接下来 行, 个长度为 的字符串。
第 行一个整数 ,表示 次询问。
最后 行,每行两个整数 和 。
输出格式
输出 行,如果他不能从城市 前往城市 ,则第 行应输出 Impossible
;如果可以,则该行应包含按上述路线选择的 "直飞航班数量 "和 "纪念品总价值",按此顺序排列,中间用空格隔开。
样例
5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5
1 100
2 160
3 180
对于 来说,有一个从城市 到城市 的直达航班,所以直达航班的最少可能数量是 ,当他使用该直达航班时,就达到了这个数量。在这种情况下,纪念品的总价值为 。
对于 ,直飞航班的最少可能数量为 。以下两条线路达到了最小值:城市 和城市 。由于这两条路线的纪念品总价值分别为 和 ,所以他选择了后一条路线,纪念品的总价值为 。
对于 ,当他前往城市 时,直达航班的数量最少,纪念品的总价值为 。
2
100 100
NN
NN
1
1 2
Impossible
数据范围
- 是一个长度为 的字符串,由
Y
和N
组成。 - 的 -th 字符是
N
。 - 如果是 ,那么就是 。
- 和 都是整数。