#P11006. [蓝桥杯 2024 省 Python B] 纯职业小组

[蓝桥杯 2024 省 Python B] 纯职业小组

题目描述

在蓝桥王国,国王统治着一支由 nn 个小队组成的强大军队。每个小队都由 相同职业的士兵组成。具体地,第 ii 个小队包含了 bib_i 名职业为 aia_i 的士兵。

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

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

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

输入格式

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

接下来依次描述 TT 组数据。

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

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

输出格式

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

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

8
-1

提示

对于 50%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}$。

样例解释

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

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