Berland 商店出售 $$$n$$$ 种果汁。每种果汁都有其价格$$$c_i$$$。每种果汁都含有一些维生素。维生素分为三种:维生素“A”、维生素“B”和维生素“C”。每种果汁都可以含有一种、两种或全部三种维生素。
Petya 知道他需要所有三种维生素才能保持健康。为了获得所有三种维生素,Petya 必须购买的果汁的最低总价是多少?如果佩蒂亚购买至少一种含有维生素的果汁并饮用,他就会获得一些维生素。
输入
第一行包含一个整数 $$$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$$$ 中字母的顺序是任意的。
输出
如果无法获得全部三种维生素,则打印 -1。否则,请打印 Petya 为获得所有三种维生素而必须购买的果汁的最低总价。
示例
输入 #1
4 5 C 6 B 16 BAC 4 A
输出 #1
15
输入 #2
2 10 AB 15 BA
输出 #2
-1
输入 #3
5 10 A 9 BC 11 CA 4 A 5 B
输出 #3
13
输入#4
6 100 A 355 BCA 150 BC 160 AC 180 B 190 CA
输出#4
250
输入 #5
2 5 BA 11 CB
输出 #5
16
注意
在第一个示例中,Petya 购买了第一、第二和第四种果汁。他花费了 $$$5 + 6 + 4 = 15$$$ 并获得了全部三种维生素。他还可以只购买第三种果汁并获得三种维生素,但其成本为 $$$16$$$,这不是最佳选择。
在第二个示例中,Petya 无法获得全部三种维生素,因为没有果汁含有维生素“C”。