当前没有测试数据。

问题描述

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

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

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

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

输入格式

输入包含多组数据。

第一行包含一个整数 $T$，表示有 $T$ 组数据。

对于每组数据：

• 第一行包含两个整数 $n_t$​ 和 $k$，表示小队的数量和要组成的纯职业小组的数量。
• 接下来的 $n_t$​ 行，每行包含两个整数 $a_i$​ 和 $b_i$​，表示第 $i$ 个小队中士兵的职业和数量。

输出格式

对于每组数据，输出一个整数，表示为了组成 $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。

评测用例规模与约定

对于 $50\%$ 的评测用例，$1≤T≤10$，$1≤\sum _{t=1}^Tn_t≤2×10^3$，$1≤a_i,b_i≤10^5$，$1≤k≤10^7$。

对于所有的评测用例，$1≤T≤100$，$1≤\sum_{t=1}^Tn_t≤2×10^5$，$1≤a_i,b_i≤10^9$，$1≤k≤10^{13}$。