AT_indeednow_2015_finalb_c Palindrome Concatenation

[problemUrl]: https://atcoder.jp/contests/indeednow-finalb-open/tasks/indeednow_2015_finalb_c Indeed 社の社員である A さんは、文字列処理のスキルを磨いています。A さんが今取り組んでいる問題は以下のようなものです。 いくつかの回文を繋げて文字列を作りたい。長さ $ i $ の回文を使うとコストが $ C_i $ かかる。このとき、文字列 $ S $ を作るために必要なコストの和の最小値を求めよ。ただし、回文とは前から読んでも後ろから読んでも同じであるような文字列である。また、同じ回文を $ 2 $ 回以上使う場合でも、使った回数分だけのコストがかかることに注意せよ。 しかしながら、A さんはこの問題を解くことができませんでした。A さんのかわりにこの問題を解くプログラムを書いてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ C_1 $ $ C_2 $ ... $ C_N $ - $ 1 $ 行目には、文字列 $ S $ の長さを表す整数 $ N\ (1\ ≦\ N\ ≦\ 5000) $ が与えられる。 - $ 2 $ 行目には、文字列 $ S $ が与えられる。$ S $ は小文字アルファベット (`a`-`z`) のみからなる長さ $ N $ の文字列である。 - $ 3 $ 行目には、回文を使うためのコストを表す $ N $ 個の整数が空白区切りで与えられる。このうち $ i\ (1\ ≦\ i\ ≦\ N) $ 番目の整数 $ C_i\ (1\ ≦\ C_i\ ≦\ 10^5) $ は、長さ $ i $ の回文を使うためのコストを表す。

いくつかの回文を繋げて文字列 $ S $ を作るときに必要なコストの和の最小値を $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 200 $ を満たすデータセット $ 1 $ に正解した場合は、$ 40 $ 点が与えられる。 - 全てのテストケースに正解した場合は、上記とは別に $ 60 $ 点が与えられる。 ### Sample Explanation 1 この入力例では、`i` + `ndeedn` + `o` + `w` のように繋ぐとコストが $ 4 $ となります。 ### Sample Explanation 2 この入力例では、`i` + `ndeedn` + `o` + `w` のように繋ぐとコストが $ 129 $ となりますが、 `i` + `n` + `d` + `ee` + `d` + `n` + `o` + `w` のように繋ぐとコストが $ 74 $ となります。