{"raw_statement":[{"iden":"problem statement","content":"We have $N$ strings of lowercase English letters: $S_1, S_2, \\cdots, S_N$.\nTakahashi 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.\nThe 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.\nFind the minimum total cost needed to choose strings so that Takahashi can make a palindrome.\nIf there is no choice of strings in which he can make a palindrome, print $-1$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 50$\n*   $1 \\leq |S_i| \\leq 20$\n*   $S_i$ consists of lowercase English letters.\n*   $1 \\leq C_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S_1$ $C_1$\n$S_2$ $C_2$\n$:$\n$S_N$ $C_N$"},{"iden":"sample input 1","content":"3\nba 3\nabc 4\ncbaa 5"},{"iden":"sample output 1","content":"7\n\nWe have `ba`, `abc`, and `cbaa`.\nFor 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.\nWe cannot make a palindrome for a cost less than $7$, so we should print $7$."},{"iden":"sample input 2","content":"2\nabcab 5\ncba 3"},{"iden":"sample output 2","content":"11\n\nWe 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$."},{"iden":"sample input 3","content":"4\nab 5\ncba 3\na 12\nab 10"},{"iden":"sample output 3","content":"8\n\nWe can choose `a` once, which is already a palindrome, but it is cheaper to concatenate `ab` and `cba`."},{"iden":"sample input 4","content":"2\nabc 1\nab 2"},{"iden":"sample output 4","content":"\\-1\n\nWe cannot make a palindrome, so we should print $-1$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}