← 返回题目列表

Codeforces · 1042/B

B. 维生素

中文机器翻译题面 查看原题

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”。