CF1042B.Vitamins

Berland shop sells $n$ kinds of juices. Each juice has its price $c_i$. Each juice includes some set of vitamins in it. There are three types of vitamins: vitamin "A", vitamin "B" and vitamin "C". Each juice can contain one, two or all three types of vitamins in it.

Petya knows that he needs all three types of vitamins to stay healthy. What is the minimum total price of juices that Petya has to buy to obtain all three vitamins? Petya obtains some vitamin if he buys at least one juice containing it and drinks it.

Berland 商店出售 $n$ 种果汁。每种果汁都有其价格 $c_i$。每种果汁包含某些种类的维生素。维生素共有三种类型：“A”、“B” 和 “C”。每种果汁可能包含其中一种、两种或全部三种维生素。

Petya 知道，为了保持健康，他必须摄入全部三种维生素。那么 Petya 需要购买的果汁的最低总价格是多少？当 Petya 购买并饮用了至少一种含有某种维生素的果汁时，即视为获得了该种维生素。

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.

第一行包含一个整数 $n$（$1 \le n \le 1\,000$）—— 果汁的种类数。

接下来的 $n$ 行中，每行包含一个整数 $c_i$（$1 \le c_i \le 100\,000$）和一个字符串 $s_i$ —— 分别表示第 $i$ 种果汁的价格及其所含的维生素。字符串 $s_i$ 的长度为 $1$ 至 $3$，且其中仅包含字符 "A"、"B" 和 "C"。保证在每个字符串 $s_i$ 中，每个字母至多出现一次。字符串 $s_i$ 中字母的顺序是任意的。

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.

如果无法获得全部三种维生素，则输出 -1。否则，输出 Petya 为获得全部三种维生素所需购买的果汁的最低总价格。

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".

在第一个例子中，Petya 购买了第一、第二和第四种果汁。他花费了 $5 + 6 + 4 = 15$，并获得了全部三种维生素。他也可以仅购买第三种果汁来获得全部三种维生素，但其成本为 $16$，并非最优解。

在第二个例子中，Petya 无法获得全部三种维生素，因为没有任何一种果汁含有维生素 “C”。