{"problem":{"name":"Making Palindrome","description":{"content":"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 chose","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc175_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc175_f","tags":[],"sample_group":[["3\nba 3\nabc 4\ncbaa 5","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$."],["2\nabcab 5\ncba 3","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$."],["4\nab 5\ncba 3\na 12\nab 10","8\n\nWe can choose `a` once, which is already a palindrome, but it is cheaper to concatenate `ab` and `cba`."],["2\nabc 1\nab 2","\\-1\n\nWe cannot make a palindrome, so we should print $-1$."]],"created_at":"2026-03-03 11:01:14"}}