← 返回题目列表

Codeforces · 1829/C

C. 完美先生

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

维克多想成为“完美先生”。为此,他需要获得一定的技能。更准确地说,他拥有他需要获得的 $$$2$$$ 技能。

维克多有 $$$n$$$ 本书。阅读 $$$i$$$ 这本书需要他 $$$m_i$$$ 分钟,并且会给他所需的两项技能中的一些(可能没有),由长度为 $$$2$$$ 的二进制字符串表示。

维克多掌握全部这两项技能所需的最短时间是多少?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 可用书籍的数量。

然后是 $$$n$$$ 行。 $$$i$$$ 行包含一个正整数 $$$m_i$$$ ($$$1 \leq m_i \leq 2 \cdot 10^5$$$) 和一个长度为 $$$2$$$ 的二进制字符串,其中 $$$s_{i1} = 1$$$ 如果阅读书籍 $$$i$$$ 获得 Victor 技能 $$$1$$$,并且 $$$s_{i1} =否则为 0$$$,如果阅读书籍 $$$i$$$ 获得维克多技能 $$$2$$$,则 $$$s_{i2} = 1$$$,否则 $$$s_{i2} = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示 Victor 获得所需技能所需的最短分钟数,并输出 $$$-1$$$,以防在阅读任何数量的书籍后无法获得这两项技能。

示例

输入 #1

6
4
2 00
3 10
4 01
4 00
5
3 01
3 01
5 01
2 10
9 10
1
5 11
3
9 11
8 01
7 10
6
4 01
6 01
7 01
8 00
9 01
1 00
4
8 00
9 10
9 11
8 11

输出 #1

7
5
5
9
-1
8

注意

在第一个测试用例中,我们可以使用书籍 $$$2$$$ 和 $$$3$$$,总共花费的分钟数等于 $$$3 + 4 = 7$$$。

在第二个测试用例中,我们可以使用书籍 $$$1$$$ 和 $$$4$$$,总共花费的分钟数等于 $$$3 + 2 = 5$$$。

在第三个测试用例中,我们只有一个选择,那就是阅读 $$$1$$$ 的书,总花费的分钟数等于 $$$5$$$。