题目描述

Victor 想成为“Mr. Perfectly Fine”。为此，他需要掌握一组特定的技能。更准确地说，他需要掌握 $2$ 项技能。

Victor 有 $n$ 本书。阅读第 $i$ 本书需要 $m_i$ 分钟，并且能让他获得一些（可能没有）所需的两项技能，这些技能由一个长度为 $2$ 的二进制字符串表示。

请问 Victor 至少需要多少分钟，才能获得全部两项技能？

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示可用的书本数量。

接下来的 $n$ 行，每行包含一个正整数 $m_i$（$1 \leq m_i \leq 2 \times 10^5$）和一个长度为 $2$ 的二进制字符串。如果 $s_{i1} = 1$，则阅读第 $i$ 本书可以获得 Victor 的第 $1$ 项技能，否则不能；如果 $s_{i2} = 1$，则阅读第 $i$ 本书可以获得 Victor 的第 $2$ 项技能，否则不能。

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

输出格式

对于每个测试用例，输出一个整数，表示 Victor 获得全部所需技能所需的最少分钟数。如果无论读多少本书都无法获得全部两项技能，则输出 $-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$ 分钟。

由 ChatGPT 4.1 翻译

来源

Codeforces 1829C，英文题名 Mr. Perfectly Fine。