codeforces#P1829C. Mr

    ID: 33807 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>bitmasksbitmasksbitmasksgreedyimplementation

Mr

Description

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?

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$.

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.

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.

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

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$.