C - 積み上げパズル Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君はある日、以下のようなゲームで遊ぶことにしました。
m 色のブロックが n 個、1 つずつ順番に落ちてきます。
1 つ落ちてくるたびに、高橋君は落ちてきたそのブロックを取って山に積むか、積まずに捨てるか選べます。
ブロックを積む山は 1 つで、ブロックは必ず山の一番上に積まないといけません。
全てのブロックが落ちきった後、出来た山は以下のように評価されます。
  • 色ボーナス：色ごとに決められた得点が、山に含まれている個数分与えられます。
  • コンボボーナス：同じ色のブロックが x 個続いて積まれている場合、コンボボーナス配点 Y に応じて Y×(x-1) 点が与えられます。
  • 全色ボーナス：山の中に m 色のブロックがそれぞれ 1 個以上含まれていると Z 点が与えられます。
落ちてくるブロックの種類と順番、またそれぞれ山を評価するための配点が与えられたとき、評価で得ることのできる最高得点を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。 
n m Y Z
c_1 p_1
c_2 p_2
:
:
c_m p_m
b_1b_2 ‥‥ b_n
  • 1 行目に n, m, Y, Z が半角スペースで区切られて与えられる。
    1. n はブロックの個数で 1≦n≦5,000 を満たす。
    2. m はブロックの色の総数で 1≦m≦10 を満たす。
    3. Y はコンボボーナス配点で -100≦Y≦100 を満たす。
    4. Z は全色ボーナス配点で -10,000≦Z≦10,000 を満たす。
    5. n, m, Y, Z は全て整数である。
  • 2 行目からの m+1 行目までの m 行で色ボーナスの配点がそれぞれ与えられる。
    1. c_i は i(1≦i≦m) 番目に与えられるブロックの色である。
    2. p_i は c_i に対する色ボーナスの配点である。
    3. c_i は英大文字(A-Z)、p_i は -100≦p_i≦100 を満たす。
    4. 配点は重複して与えられない（x≠y ならば c_x≠c_y)
  • m+2 行目には落ちてくるブロックの順序を表す長さ n の文字列が与えられる。
    1. b_j は j(1≦j≦n) 番目に落ちてくるブロックの色を表している。
    2. b_j は c_1,c_2,...,c_m のいずれかである。

出力

評価で得ることのできる得点の最大値を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

5 3 3 5
R 1
G 1
B 1
RGBRR

出力例 1

13
  • 全てのブロックを山に積むと、
    • 色ボーナス：どの色も配点が 1 点なので、1 点 × 5 個 = 5点
    • コンボボ−ナス：Rが 2 個連続しているので、3×(2-1)=3 点
    • 全色ボーナス：全ての色が 1 つ以上山に積まれているので、5 点
    により、5+3+5=13 点が与えられます。
  • いずれかのブロックを捨てるとこの点数よりも低くなるので、答えは 13 点です。

入力例 2

3 3 3 5
R 1
G 3
B 2
RBR

出力例 2

5
  • 全てのブロックを山に積むと、
    • 色ボーナス：1 点 ×2 個 +2 点 ×1 個 =4 点
    • 連続していないのでコンボボーナス、Gが含まれていないので全色ボーナスはそれぞれ 0 点
    により、4 点です。
  • しかし、Bを捨ててRRを山に積むと、
    • 色ボーナス：1 点 ×2 個 =2 点
    • コンボボーナス：3×(2-1)=3 点
    で、5 点が最高得点です。

入力例 3

8 3 5 3
R 1
G 1
B 1
RRGRRBRR

出力例 3

31
  • 図 (a) のように順に 8 個のブロックが落ちてきます。
  • ブロックを全部山に積むと、図 (b) のように、2 個のコンボが 3 組できます。
  • また、全色ボーナスもつくので、1 点 × 8 個 + 5 点 × (2-1) × 3 組 + 3 点 = 26 点です。
  • しかし、図 (c) のようにRのみを山に積むと、1 点 × 6 個 + 5 点 × (6-1) + 0 点 = 31 点になります。
  • Rだけ山に積むとき最高得点となり、31 が答えです。

入力例 4

8 3 5 3
R 1
G 100
B 1
RRGRRBRR

出力例 4

126
  • 全部積んだ場合(図 (a))：107 点 + 5 点 × (2-1) × 3 組 + 3 点 = 125 点
  • Rのみを積んだ場合(図 (b))：6 点 + 5 点 × (6-1) + 0 点 = 31 点
  • B以外を積んだ場合(図 (c))：106 点 + 5 点 × \{(2-1) + (4-1)\} + 0 点 = 126 点
  • したがって、最高得点は 126 点です。