贝尔兰陆军正在准备大型阅兵。已经决定参加的士兵将被分为$$$k$$$行,并且所有行将包含相同数量的士兵。
当然,并非每种将士兵排列成 $$$k$$$ 行的方式都是合适的。同一排中所有士兵的身高差异不应超过 $$$1$$$。每个士兵的身高是 $$$1$$$ 到 $$$n$$$ 之间的整数。
对于每个可能的高度,您知道具有该高度的士兵的数量。要进行游行,您必须选择参加游行的士兵,然后将所有选定的士兵排列成 $$$k$$$ 行,以便满足以下两个条件:
- 每行都有相同数量的士兵,
- 没有一行包含一对身高相差 $$$2$$$ 或更多的士兵。
计算可以参加阅兵的最大士兵人数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 测试用例的数量。然后是测试用例。
每个测试用例都以包含两个整数 $$$n$$$ 和 $$$k$$$ 的行开始($$$1 \le n \le 30000$$$, $$$1 \le k \le 10^{12}$$$)——分别是不同身高士兵的数量和游行中士兵的行数。
每个测试用例的第二行(也是最后一行)包含 $$$n$$$ 整数 $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ ($$$0 \le c_i \le 10^{12}$$$),其中 $$$c_i$$$ 是 Berland 身高 $$$i$$$ 的士兵数量军队。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$30000$$$。
输出
对于每个测试用例,打印一个整数——可以参加阅兵的最大士兵数量。
示例
输入 #1
5 3 4 7 1 13 1 1 100 1 3 100 2 1 1000000000000 1000000000000 4 1 10 2 11 1
输出 #1
16 100 99 2000000000000 13
注意
示例测试用例的说明:
1. 行中士兵的身高可以为:$$$[3, 3, 3, 3]$$$, $$$[1, 2, 1, 1]$$$, $$$[1, 1, 1, 1]$$$, $$$[3, 3, 3, 3]$$$(每个列表代表一行);
2.所有士兵可以在同一排行进;
3. 每 $$$3$$$ 行中有 $$$33$$$ 身高 $$$1$$$ 的士兵;
4.所有士兵可以在同一排行进;
5.身高$$$2$$$和$$$3$$$的士兵可以在同一排行进。