维克多想成为“完美先生”。为此,他需要获得一定的技能。更准确地说,他拥有他需要获得的 $$$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$$$。