310409: CF1829C. Mr. Perfectly Fine

C. Mr. Perfectly Finetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Victor wants to become "Mr. Perfectly Fine". For that, he needs to acquire a certain set of skills. More precisely, he has $2$ skills he needs to acquire.

Victor has $n$ books. Reading book $i$ takes him $m_i$ minutes and will give him some (possibly none) of the required two skills, represented by a binary string of length $2$.

What is the minimum amount of time required so that Victor acquires all of the two skills?

Input

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of books available.

Then $n$ lines follow. Line $i$ contains a positive integer $m_i$ ($1 \leq m_i \leq 2 \cdot 10^5$) and a binary string of length $2$, where $s_{i1} = 1$ if reading book $i$ acquires Victor skill $1$, and $s_{i1} = 0$ otherwise, and $s_{i2} = 1$ if reading book $i$ acquires Victor skill $2$, and $s_{i2} = 0$ otherwise.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer denoting the minimum amount of minutes required for Victor to obtain both needed skills and $-1$ in case it's impossible to obtain the two skills after reading any amount of books.

ExampleInput

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

Output

7
5
5
9
-1
8

Note

In the first test case, we can use books $2$ and $3$, with a total amount of minutes spent equal to $3 + 4 = 7$.

In the second test case, we can use the books $1$ and $4$, with a total amount of minutes spent equal to $3 + 2 = 5$.

In the third test case, we have only one option and that is reading book $1$ for a total amount of minutes spent equal to $5$.

**题目大意：**

Victor想要成为“完美先生”，为此，他需要获得特定的技能，具体来说，他需要获得2种技能。Victor有`n`本书，读第`i`本书需要`m_i`分钟，并且会给他一些（可能没有）所需的两项技能，用长度为2的二进制字符串表示。

问：Victor最少需要多少时间才能获得这两项技能？

**输入数据格式：**

输入由多个测试案例组成。第一行包含一个整数`t`（`1 ≤ t ≤ 1000`）——测试案例的数量。接下来是每个测试案例的描述。

每个测试案例的第一行包含一个整数`n`（`1 ≤ n ≤ 2 × 10^5`）——可用书籍的数量。

然后是`n`行。第`i`行包含一个正整数`m_i`（`1 ≤ m_i ≤ 2 × 10^5`）和一个长度为2的二进制字符串，其中`s_{i1} = 1`如果读第`i`本书可以获得Victor技能1，否则`s_{i1} = 0`，并且`s_{i2} = 1`如果读第`i`本书可以获得Victor技能2，否则`s_{i2} = 0`。

保证所有测试案例的`n`之和不超过`2 × 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`。**题目大意：** Victor想要成为“完美先生”，为此，他需要获得特定的技能，具体来说，他需要获得2种技能。Victor有`n`本书，读第`i`本书需要`m_i`分钟，并且会给他一些（可能没有）所需的两项技能，用长度为2的二进制字符串表示。 问：Victor最少需要多少时间才能获得这两项技能？ **输入数据格式：** 输入由多个测试案例组成。第一行包含一个整数`t`（`1 ≤ t ≤ 1000`）——测试案例的数量。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数`n`（`1 ≤ n ≤ 2 × 10^5`）——可用书籍的数量。 然后是`n`行。第`i`行包含一个正整数`m_i`（`1 ≤ m_i ≤ 2 × 10^5`）和一个长度为2的二进制字符串，其中`s_{i1} = 1`如果读第`i`本书可以获得Victor技能1，否则`s_{i1} = 0`，并且`s_{i2} = 1`如果读第`i`本书可以获得Victor技能2，否则`s_{i2} = 0`。 保证所有测试案例的`n`之和不超过`2 × 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`。