题目描述

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

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

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

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

输入格式

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

接下来依次描述 $T$ 组数据。

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

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

输出格式

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

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

8
-1

提示

对于 $50\%$ 的评测用例，$1\le T \le 10，1 \le \sum_{t=1}^Tn_t \le 2 \times 10^3,1 \le ai , b_i \le 10^5,1 \le k \le 10^7$。

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

样例解释

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

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