隧道挖掘

Problem Description

小 $\mathcal{L}$ 需要挖 $n$ 条隧道，第 $i$ 条隧道长度为 $a_i$ 米。现在小 $\mathcal{L}$ 可以购买两种挖掘设备。 对于第一种设备，包含正整数参数 $k_1$。每天可以挖掘任意隧道 $k_1$ 米，如果剩余长度不足 $k_1$ 米则会将其挖完，但是要求隧道初始长度不小于 $\mathbf{k_1}$ 米。 对于第二种设备，包含正整数参数 $k_2$。每天可以挖掘任意隧道 $k_2$ 米，但是要求隧道需要挖掘的剩余长度不小于 $\mathbf{k_2}$ 米。 对于每一天，小 $\mathcal{L}$ 只能选择其中一种机器对一条隧道进行施工。 现在你需要帮小 $\mathcal{L}$ 选择适合的机器的参数（选择后不能变更），可以在最短的时间内挖掘完所有隧道。

Input

第一行一个整数 $t$（$1\leq t\leq 1000$），表示测试数据组数。 接下来对于每一组数据，第一行两个整数 $n,m$（$1\leq n,m\leq 10^6$），分别表示隧道的条数与隧道长度的限制。 接下来一行包含 $n$ 个整数 $a_i$（$1\leq a_i\leq m$），依次表示每一条隧道的长度。 保证所有测试数据的 $n$ 的和与 $m$ 的和分别不超过 $5\times 10^6$。

Output

对于每一组数据输出一行，表示最短的时间。

Sample Input

4
5 5
1 4 4 2 3
5 11
3 6 9 10 11
4 2
1 2 1 2
6 5
1 1 4 5 1 4

Sample Output

8
8
4
7

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）