Vitamins

Description:

Input:

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 1\,000)$$$ — the number of juices.

Each of the next $$$n$$$ lines contains an integer $$$c_i$$$ $$$(1 \le c_i \le 100\,000)$$$ and a string $$$s_i$$$ — the price of the $$$i$$$-th juice and the vitamins it contains. String $$$s_i$$$ contains from $$$1$$$ to $$$3$$$ characters, and the only possible characters are "A", "B" and "C". It is guaranteed that each letter appears no more than once in each string $$$s_i$$$. The order of letters in strings $$$s_i$$$ is arbitrary.

Output:

Print -1 if there is no way to obtain all three vitamins. Otherwise print the minimum total price of juices that Petya has to buy to obtain all three vitamins.

Sample Input:

4
5 C
6 B
16 BAC
4 A

Sample Output:

15

Sample Input:

2
10 AB
15 BA

Sample Output:

-1

Sample Input:

5
10 A
9 BC
11 CA
4 A
5 B

Sample Output:

13

Sample Input:

6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA

Sample Output:

250

Sample Input:

2
5 BA
11 CB

Sample Output:

16

Note:

In the first example Petya buys the first, the second and the fourth juice. He spends $$$5 + 6 + 4 = 15$$$ and obtains all three vitamins. He can also buy just the third juice and obtain three vitamins, but its cost is $$$16$$$, which isn't optimal.

In the second example Petya can't obtain all three vitamins, as no juice contains vitamin "C".