001 - Three Color Reduction

問題文

　'$\text{A}$', '$\text{B}$', '$\text{C}$', '$\text{?}$' からなる長さ $N$ の文字列 $S$ が与えられます。 $S$ に含まれるすべての '$\text{?}$' を独立に '$\text{A}$', '$\text{B}$', '$\text{C}$' のいずれかの文字に置き換えます。文字列 $S$ に含まれる '$\text{?}$' の個数を $K$ としたとき、$i$ 番目($1 \leq i \leq K$)の '$\text{?}$' を '$\text{A}$', '$\text{B}$', '$\text{C}$' に置き換えるためにかかるコストは、それぞれ $A_i, B_i, C_i$ です。

　'$\text{?}$'を置き換えて得られる文字列のうち、以下の 3 つの操作のいずれかを選んで繰り返し行うことで空文字列にできるものについて、置き換えにかかる合計コストの最小値を求めてください。 ただし、どのように操作を行っても空文字列にできない場合は -1 を出力してください。

• 連続する同じ 2 文字を消す。
• 「$\text{X}\text{Y}\text{X}$」の形の 3 文字を、残りの文字 1 文字に置き換える。
• 3 種類の文字がすべて異なる 3 文字を、真ん中の文字 1 文字に置き換える。

制約

• $1 \le N \le 2 \times 10^5$
• $0 \le A_i, B_i, C_i \le 10^9$
• $S$ は'$\text{A}$', '$\text{B}$', '$\text{C}$', '$\text{?}$' からなる長さ $N$ の文字列
• 入力はすべて整数である

入出力

入力

入力は以下の形式で標準入力から与えられる。
ここで $K$ は文字列 $S$ に含まれる '$\text{?}$' の個数とする。

N
S
A_1 B_1 C_1
A_2 B_2 C_2
...
A_K B_K C_K

出力

空文字列にできるような置き換えにかかる合計コストの最小値を出力せよ。不可能である場合は -1 を出力せよ。

サンプル

入力例 1

4
A?B?
10 20 30
40 50 60

出力例 1

60

1つ目の '?' を 'B' に（コスト20）、2つ目の '?' を 'A' に（コスト40）置き換えると、文字列は "ABBA" となります。
"ABBA" は中央の "BB" を消去して "AA" になり、さらに "AA" を消去することで空文字列にできます。
このときのコストは $20 + 40 = 60$ となり、これが最小です。

入力例 2

3
???
1 1 1
1 1 1
1 1 1

出力例 2

-1

長さ3の文字列は、どのように操作を行っても空文字列にすることはできません。

入力例 3

2
C?
100 200 300

出力例 3

300

提出

提出はこちらから行えます。