A15896 | Mr. Perfectly Fine

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.