/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 を出力せよ。
入力例 1
3 ba 3 abc 4 cbaa 5
出力例 1
7
ba, abc, cbaa があります。
例えば、ba, abc を 1 個ずつ使うとコストは 7 で、abc, ba の順で連結すると回文になります。
また、abc, cbaa を 1 個ずつ使うとコストは 9 で、cbaa, abc の順で連結すると回文になります。
コスト 7 未満で回文を作ることはできないので、7 を出力してください。
入力例 2
2 abcab 5 cba 3
出力例 2
11
abcab を 1 個、cba を 2 個選んで、abcab, cba, cba の順で連結すると回文になり、コストは 11 です。
入力例 3
4 ab 5 cba 3 a 12 ab 10
出力例 3
8
a を 1 個だけ選んで回文とすることもできますが、ab と cba を選んで連結する方がコストが小さいです。
入力例 4
2 abc 1 ab 2
出力例 4
-1
回文を作ることが不可能であるので、-1 を出力してください。
Score : 600 points
Problem Statement
We have N strings of lowercase English letters: S_1, S_2, \cdots, S_N.
Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.
The cost of using the string S_i once is C_i, and the cost of using it multiple times is C_i multiplied by that number of times.
Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.
If there is no choice of strings in which he can make a palindrome, print -1.
Constraints
- 1 \leq N \leq 50
- 1 \leq |S_i| \leq 20
- S_i consists of lowercase English letters.
- 1 \leq C_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N S_1 C_1 S_2 C_2 : S_N C_N
Output
Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or -1 if there is no such choice.
Sample Input 1
3 ba 3 abc 4 cbaa 5
Sample Output 1
7
We have ba, abc, and cbaa.
For example, we can use ba once and abc once for a cost of 7, then concatenate them in the order abc, ba to make a palindrome.
Also, we can use abc once and cbaa once for a cost of 9, then concatenate them in the order cbaa, abc to make a palindrome.
We cannot make a palindrome for a cost less than 7, so we should print 7.
Sample Input 2
2 abcab 5 cba 3
Sample Output 2
11
We can choose abcab once and cba twice, then concatenate them in the order abcab, cba, cba to make a palindrome for a cost of 11.
Sample Input 3
4 ab 5 cba 3 a 12 ab 10
Sample Output 3
8
We can choose a once, which is already a palindrome, but it is cheaper to concatenate ab and cba.
Sample Input 4
2 abc 1 ab 2
Sample Output 4
-1
We cannot make a palindrome, so we should print -1.