1472. 迪奥娜的调酒配方

迪奥娜一直在为了调制出难喝的酒而努力。在上次用蜥蜴尾巴、史莱姆凝胶、蝴蝶翅膀来调制依旧失败后,迪奥娜又找到了一种调制难喝的酒的方法。

这种方法是,每种调酒用的调料只放一份量的进去。

所以现在每杯酒要放 m 份量的调料,且放入的每份调料的种类各不相同。

再给出 n 种调料,以及每种调料现有的份量数,求最多能调制出多少杯酒。

输入

第一行T表示测试样例数。(1 \leq T \leq 10)

对于每个测试样例:

第一行 n,m ,表示调料的种类数和每杯酒要放的份量数。 (1 \leq n \leq 10^6, 1 \leq m \leq 3 \times 10^5)

第二行有 n 个整数 a_i(1 \leq a_i \leq 10^{10}),表示第 i 种调料的份量数。且份量数是随着 i 递增的。

输出

对于每个测试样例,输出一行,包含一个数字,代表最多能调制出多少杯酒。

样例

标准输入 复制文本
2
7 4
1 2 2 3 6 9 10
6 3
2 2 6 6 7 8
标准输出 复制文本
7
10

来源

2021 软件学院 ACM 集训队筛选赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 118
通过 20