迪奥娜一直在为了调制出难喝的酒而努力。在上次用蜥蜴尾巴、史莱姆凝胶、蝴蝶翅膀来调制依旧失败后,迪奥娜又找到了一种调制难喝的酒的方法。
这种方法是,每种调酒用的调料只放一份量的进去。
所以现在每杯酒要放 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 集训队筛选赛