409834: GYM103800 K Ginger's palindrome

Ginger has $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$, the value of $$$a_i$$$ is $$$c_{i}$$$. Ginger will choose some of these numbers so that put together it is a palindrome, the same number can be chose multiple times.

Ginger wants to know the minimum value.

The first line contain a integer $$$n$$$ $$$(1\le n \le 40)$$$ indicate number of numbers.

The next $$$n$$$ line, each line contains two integers $$$a_i, c_i$$$ $$$(0\le a_i, c_i \le10^{9})$$$

Print the minimum value.

5
12 21
21 13
13 111
45 19
331 12

34

If there is a number chose multiple times, the value is the value of the number $$$\times$$$ number of choices.