纯职业小组

题号：NC309568
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

在蓝桥王国，国王统治着一支由 $n$ 个小队组成的强大军队。每个小队都由**相同职业**的士兵组成。具体地，第 $i$ 个小队包含了 $b_i$ 名职业为 $a_i$ 的士兵。

近日，国王计划在王宫广场举行一场盛大的士兵检阅仪式，以庆祝王国的繁荣昌盛。然而，在士兵入场的过程中，一场突如其来的风暴打乱了他们的行列，使得不同小队的士兵混杂在一起，次序乱成一团。

尽管国王无法知道每个士兵的具体职业，但为了确保仪式顺利进行，国王打算从这些混乱的士兵中选出一部分，组成 $k$ 个“纯职业小组”进行检阅。一个“纯职业小组”定义为由 **3 名同职业**的士兵组成的队伍。

请问，国王**至少**需要选择多少名士兵，才能**确保**这些士兵可以组成 $k$ 个“纯职业小组”？

输入描述:

输入的第一行包含一个整数 ，表示每次输入包含  组数据。

接下来依次描述  组数据。

每组数据的第一行包含两个整数  和 ，用一个空格分隔，表示小队的数量和要组成的纯职业小组的数量。

接下来  行，每行包含两个整数  和 ，用一个空格分隔，表示第  个小队中士兵的职业和数量。

输出描述:

输出  行，每行包含一个整数，依次表示每组数据的答案。即为了组成  个“纯职业小组”，国王至少需要选择的士兵数量。如果无论如何也无法组成  个“纯职业小组”，则输出 。

示例1

输入

复制

输出

复制

8
-1

说明

在第一个样例中，要想组成 2 个“纯职业小组”，国王至少需要选择 8 名士兵。若只选择 7 名士兵，则 7 名士兵的职业可能为 1, 1, 1, 2, 2, 3, 3，无法组成 2 个“纯职业小组”。

在第二个样例中，即使选择了所有士兵，也无法组成 5 个“纯职业小组”，因此输出 -1。

备注:

- 对于 50% 的评测用例，。
- 对于所有评测用例，。