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