Responsive image

问题 H: 完美先生(思维)

问题 H: 完美先生(思维)

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

维克多想成为 "完美先生"。为此，他需要掌握一定的技能。更准确地说，他有两个项技能，他需要获得这些技能。
维克多有n本书。阅读第i本书需要花费mi分钟，阅读完将使他获得所需的两种技能中的一部分（可能没有），用一个长度为2的二进制字符串表示.
为了使维克多获得所有的两种技能，所需的最少时间是多少？

输入描述

输入由多个测试案例组成。第一行包含一个整数t（1≤t≤1000)--测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数n（1≤n≤2⋅105)--可用书籍的数量。
然后是n行。第i行包含一个正整数mi（1≤mi≤2⋅105）和一个长度为2的二进制字符串，其中如果Si1=1，则阅读第i本书可获得技能1，若Si1=0，则无法获得技能1.如果Si2=1,则阅读第i本书可获得技能2，若Si2=0则无法获得技能2。
可以保证所有测试案例的n之和不超过2⋅105。

输出描述

对于每个测试案例，输出一个整数，表示维克多获得两个所需技能所需的最少时间，如果读完任何数量的书都不可能获得这两个技能，则输出-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

样例输出

7
5
5
9
-1
8

提示

在第一个测试案例中，我们可以使用书籍2和3，所花的总时间等于3+4=7.

在第二个测试案例中，我们可以使用书籍1和4，花费的总时间等于3+2=5。.

在第三个测试案例中，我们只有一个选择，那就是阅读第1本书，所花的总时间等于5分钟。

[提交][状态]
ACM算法攻关部