该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Pénjamo商店出售 n 种果汁。每种果汁的价格为 ci。每种果汁都含有一些维生素。维生素有三种：维生素 "A"、维生素 "B" 和维生素 "C"。每种果汁可以含有一种、两种或全部三种维生素。

Petya 知道他需要这三种维生素来保持健康。要获得所有三种维生素，Petya 购买果汁的最低总价是多少？如果 Petya 至少购买一种含有某种维生素的果汁并饮用，他就能获得这种维生素。

输入

第一行包含一个整数 n - 果汁的数量。 $(1 ≤ n ≤ 1000)$

接下来的每一行 n 都包含一个整数 $ci (1 ≤ ci ≤ 100000)$ 和一个字符串 $s_i$ - 果汁的价格和所含的维生素。字符串 si 包含 1 至 3 个字符，唯一可能出现的字符是 "$A$"、"$B$" 和 "$C$"。保证每个字母在每个字符串 si 中出现的次数不超过一次。字符串 $s_i$ 中字母的顺序是任意的。

输出

如果无法获得所有三种维生素，则打印 $-1$。否则打印 Petya 为获得所有三种维生素而必须购买的果汁的最低总价。

Examples

4
5 C
6 B
16 BAC
4 A

15

2
10 AB
15 BA

-1

5
10 A
9 BC
11 CA
4 A
5 B

13

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

250

2
5 BA
11 CB

16

注

在第一个例子中，Petya 购买了第一、第二和第四种果汁。他花费了 $5 + 6 + 4 = 15$ 并获得了所有三种维生素。他也可以只买第三杯果汁，获得三种维生素，但其花费为 $16$，这并不是最佳方案。

在第二个例子中，Petya 无法获得所有三种维生素，因为没有一种果汁含有维生素 "$C$"。

数据范围

$1 ≤ n ≤ 1000$

$1 ≤ ci ≤ 100000$