{"code":"makepalin","name":"MAKEPALIN","description":"Cho $n$ xâu $s_1,s_2,\\ldots,s_n$. Chi phí để sử dụng xâu $s_i$ là $c_i$.\r\nLưu ý: Có thể sử dụng xâu $s_i$ nhiều lần và chi phí là $c_i$ nhân với số lần dùng.\r\n\r\n**Yêu cầu**: Tìm chi phí tối thiểu để sử dụng các xâu $s_i$ ghép lại với nhau thành xâu đối xứng.\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa duy nhất một số nguyên dương $n$ ($1\\leq n \\leq 50$) là số lượng xâu.\r\n- Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa xâu $s_i$ và số nguyên $c_i$ là xâu thứ i và chi phí để sử dụng (1 $\\leq |s_i| \\leq 20; 1\\leq c_i \\leq 10^9$).\r\n\r\n\r\n

Output

\r\n\r\n- In ra chi phí tối thiểu, in $-1$ nếu không tạo được xâu đối xứng.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3\r\n ba 3\r\n abc 4\r\n cbaa 5\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 7\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2\r\n abcab 5\r\n cba 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 11\r\n ```\r\n \r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2\r\n abc 1\r\n ab 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n -1\r\n ```","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}