蓝桥杯2024年第十五届省赛真题-纯职业小组

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

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

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

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

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

接下来依次描述 T 组数据。每组数据的第一行包含两个整数 nt 和 k ，用一个空格分隔，表示小队的数量和要组成的纯职业小组的数量。

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

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

如果无论如何也无法组成 k个“纯职业小组”，则输出 −1。

2
3 2
1 3
2 3
3 3
3 5
1 3
2 3
3 3

8
-1

【样例说明】

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

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