配点 : $600$ 点

問題文

英小文字から成る $N$ 個の文字列 $S_1, S_2, \cdots, S_N$ があります。

高橋君はまずこれらの文字列から重複を許して合計 $1$ 個以上選んだ後、選んだ文字列を好きな順番で連結することで、回文であるような文字列を作ろうとしています。

文字列 $S_i$ を $1$ 個使うにはコストが $C_i$ かかり、同じ文字列であっても使った個数の分だけコストがかかります。

上述の方法で回文を作ることのできるように文字列を選ぶ方法のうち、コストの和としてありうる値の最小値を求めてください。

また、どのように選んでも回文を作ることが不可能である場合は $-1$ を出力してください。

制約

• $1 \leq N \leq 50$
• $1 \leq |S_i| \leq 20$
• $S_i$ は英小文字から成る
• $1 \leq C_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$S_1$ $C_1$

$S_2$ $C_2$

$:$

$S_N$ $C_N$

出力

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

3
ba 3
abc 4
cbaa 5

7

ba, abc, cbaa があります。

例えば、ba, abc を $1$ 個ずつ使うとコストは $7$ で、abc, ba の順で連結すると回文になります。 また、abc, cbaa を $1$ 個ずつ使うとコストは $9$ で、cbaa, abc の順で連結すると回文になります。

コスト $7$ 未満で回文を作ることはできないので、$7$ を出力してください。

2
abcab 5
cba 3

11

abcab を $1$ 個、cba を $2$ 個選んで、abcab, cba, cba の順で連結すると回文になり、コストは $11$ です。

4
ab 5
cba 3
a 12
ab 10

8

a を $1$ 個だけ選んで回文とすることもできますが、ab と cba を選んで連結する方がコストが小さいです。

2
abc 1
ab 2

-1

回文を作ることが不可能であるので、$-1$ を出力してください。