You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Timi在玩打怪游戏，他想升级自己的大招，但是在升级大招之前，他需要先升级$1$技能和$2$技能。

游戏中有$n$只野怪，攻击第i只野怪需要花$m_i$秒，然后获得经验，可以升级一些技能，可能是$1$技能，可能是$2$技能，可能是$1$、$2$技能，也有可能一个都升级不了，这由一个长度为$2$的二进制字符串表示。

请你帮Timi计算升级大招所需的最少时间。

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含一个整数$n$，表示野怪的数量。

每个测试用例接下来$n$行，每行包含一个正整数$m_i$，和一个长度为$2$的二进制字符串，其中$s_{i1}=1$代表Timi获得$1$技能，$s_{i1}=0$代表Timi没获得$1$技能，$s_{i2}=1$代表Timi获得$2$技能，$s_{i2}=0$代表Timi没获得$2$技能。

输出格式

对于每个测试用例，输出一个整数，表示Timi升级大招所需的最少时间，如果无论攻击多少只野怪，都无法升级大招，则输出-1。

4
4
2 00
3 10
4 01
4 00
5
3 01
3 01
5 01
2 10
9 10
1
5 11
6
4 01
6 01
7 01
8 00
9 01
1 00

7
5
5
-1

提示

【样例解释】

在第一个测试用例中，Timi可以攻击第$2$只野怪和第$3$只野怪，总共花费的时间为$3+4=7$。

在第二个测试用例中，Timi可以攻击第$1$只野怪和第$4$只野怪，总共花费的时间为$3+2=5$。

在第三个测试用例中，Timi只能攻击第$1$只野怪，总共花费的时间为$5$。

【数据范围】

对于所有数据，保证：$1 \leq t \leq 1000,1 \leq n,m_i \leq 2\cdot 10^5$。所有测试用例中$n$的总和不超过$2\cdot10^5$。