题目描述

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

Petya 知道他需要三种维生素才能保持健康。Petya 至少需要购买含有每种维生素的果汁各一瓶并饮用，才能获得所有三种维生素。那么，Petya 至少需要花多少钱才能获得全部三种维生素？

如果 Petya 购买的果汁中至少有一种含有某种维生素，他就能获得这种维生素。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 1000$），表示果汁的种类数。

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

输出格式

如果无法获得全部三种维生素，输出 $-1$。否则，输出 Petya 至少需要花费的总价格。

说明/提示

在第一个样例中，Petya 购买第 $1$、第 $2$ 和第 $4$ 种果汁，花费 $5+6+4=15$，获得全部三种维生素。他也可以只买第 $3$ 种果汁获得三种维生素，但价格为 $16$，不是最优解。

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

由 ChatGPT 4.1 翻译

样例

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