Codeforces Round 871 (Div. 4)

C. 完美先生（Mr. Perfectly Fine）

时间限制： 2 秒 内存限制： 256 MB

题目描述

Victor 想成为 “完美先生 (Mr. Perfectly Fine)”。 为此，他需要掌握 ​两项技能​。

Victor 一共有 ​n 本书​。阅读第 i 本书需要花费 mi 分钟，并且可以获得这两项技能中的某些（可能一项也没有）。

技能的获取方式由一个长度为 2 的二进制字符串表示：

• 如果字符串的第 1 位是 1，表示读这本书可以获得 ​技能 1​；否则没有。
• 如果字符串的第 2 位是 1，表示读这本书可以获得 ​技能 2​；否则没有。

Victor 想知道：至少需要多少分钟，才能掌握这两项技能？

输入格式

输入包含多个测试用例。

• 第一行包含一个整数 t (1 ≤ t ≤ 1000)，表示测试用例数量。
• 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 2×10^5)，表示书的数量。
• 接下来 n 行，每行包含：
  • 一个正整数 mi (1 ≤ mi ≤ 2×10^5)，表示阅读该书所需的分钟数；
  • 一个长度为 2 的二进制字符串。

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

输出格式

对于每个测试用例，输出一个整数，表示获得两项技能所需的最少分钟数。 如果无论读多少书都无法获得两项技能，输出 -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。
• 在第三个测试用例中，只有一本书（同时包含两项技能），总耗时 5。