### **问题描述** 在蓝桥王国，国王统治着一支由 $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\leq T\leq 10$，$1\leq \sum \limits_{t=1}^T n_t \leq 2\times 10^3$，$1\leq a_i, b_i \leq 10^5$，$1\leq k \leq 10^7$。 对于所有的评测用例，$1\leq T \leq 100$，$1\leq \sum\limits_{t=1}^T n_t \leq 2\times 10^5$，$1\leq a_i, b_i \leq 10^9$，$1\leq k \leq 10^{13}$。