题目描述

光头强想要成为完美先生。为此，他需要掌握一定的技能。更确切地说，他需要掌握 $2$ 个技能。

光头强有 $n$ 本书。阅读第 $i$ 本书需要 $m_i$ 分钟，并且将给他带来两个技能中的一些（可能是零），用长度为 $2$ 的二进制字符串表示。

求光头强获取所有两个技能所需的最短时间是多少？

输入格式

输入包含多个测试用例。第一行包含一个整数 $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$ 本书会获得光头强的技能 $1$，否则 $s_{i1}=0$，并且 $s_{i2}=1$ 如果阅读第 $i$ 本书会获得光头强的技能 $2$，否则 $s_{i2}=0$。

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

输出格式

对于每个测试用例，输出一个整数，表示光头强获取所需两个技能所需的最短时间，并在无论阅读多少书籍后无法获得两个技能时输出 -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$。