Stone祝你元宵节快乐!
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
为了庆祝正月十五的到来,Stone 决定去采购一波汤圆。在一个 n×m 的货架上,有最多26种不同口味的 cyk 色汤圆('a'~'z'),有的时候商家会出售三种特殊颜色的汤圆:柏皓色 ('H'),bLue色 ('B') 和金桔色 ('Q')。为了膜拜金桔,出现金桔色汤圆时,Stone 一定选择金桔色汤圆,否则一定买柏皓色或 bLue色汤圆(特殊汤圆至少买一个,如果没有特殊汤圆,Stone 就不会买汤圆)。Stone 会从货架的左上角 (1, 1) 位置开始到 (n, m) 位置取一条路径,路径上的每个汤圆都会取。Stone 的路径选择时,每一步只能向下或者向右,并且不能走出货架的范围。Stone 对不同的汤圆具有不同的喜好值,但是 Stone 假装不知道如何取才能使取得的汤圆的喜好值总和最大,你能帮助他吗?
Input
输入数据有多组(数据组数不超过 50),到 EOF 结束。
对于每组数据:
第一行为两个整数 n,m (1 <= n, m <= 1000)。
第二行为 26 个整数,代表 Stone 对 cyk 系列 ('a'-'z') 汤圆的喜好值。
第三行为 3 个整数,代表 Stone 对柏皓色 ('H'),bLue色 ('B') 和金桔色 ('Q') 汤圆的喜好值。
接下来 n 行,每行 m 个字符(字符在一行内连续且不含空格),代表货架上该位置的汤圆类型 ('a'-'z', 'H', 'B', 'Q')。
所有汤圆喜好值的范围都为:[-1000, 1000]。
Output
每组数据输出 Stone 购买汤圆能获得的最大喜好值。
如果 Stone 没有买汤圆,输出 "have to give up!!!"。
Sample Input
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Q 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2 0 0 1 wQy zab Qma
Sample Output
1 1
Hint
Source
【2017年寒假集训 阶段测试赛2 - 元宵节专场】Stone