AT_abc175_f [ABC175F] Making Palindrome

[problemUrl]: https://atcoder.jp/contests/abc175/tasks/abc175_f 英小文字から成る $ N $ 個の文字列 $ S_1,\ S_2,\ \cdots,\ S_N $ があります。 高橋君はまずこれらの文字列から重複を許して合計 $ 1 $ 個以上選んだ後、選んだ文字列を好きな順番で連結することで、回文であるような文字列を作ろうとしています。 文字列 $ S_i $ を $ 1 $ 個使うにはコストが $ C_i $ かかり、同じ文字列であっても使った個数の分だけコストがかかります。 上述の方法で回文を作ることのできるように文字列を選ぶ方法のうち、コストの和としてありうる値の最小値を求めてください。 また、どのように選んでも回文を作ることが不可能である場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ C_1 $ $ S_2 $ $ C_2 $ $ : $ $ S_N $ $ C_N $

回文を作ることのできるように文字列を選ぶ方法のうち、コストの和としてありうる値の最小値を出力せよ。不可能である場合は $ -1 $ を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 50 $ - $ 1\ \leq\ |S_i|\ \leq\ 20 $ - $ S_i $ は英小文字から成る - $ 1\ \leq\ C_i\ \leq\ 10^9 $ ### Sample Explanation 1 `ba`, `abc`, `cbaa` があります。 例えば、`ba`, `abc` を $ 1 $ 個ずつ使うとコストは $ 7 $ で、`abc`, `ba` の順で連結すると回文になります。 また、`abc`, `cbaa` を $ 1 $ 個ずつ使うとコストは $ 9 $ で、`cbaa`, `abc` の順で連結すると回文になります。 コスト $ 7 $ 未満で回文を作ることはできないので、$ 7 $ を出力してください。 ### Sample Explanation 2 `abcab` を $ 1 $ 個、`cba` を $ 2 $ 個選んで、`abcab`, `cba`, `cba` の順で連結すると回文になり、コストは $ 11 $ です。 ### Sample Explanation 3 `a` を $ 1 $ 個だけ選んで回文とすることもできますが、`ab` と `cba` を選んで連結する方がコストが小さいです。 ### Sample Explanation 4 回文を作ることが不可能であるので、$ -1 $ を出力してください。