K. Ginger's palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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})$$$

Output

Print the minimum value.

Example
Input
5
12 21
21 13
13 111
45 19
331 12
Output
34
Note

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