The Parade

**题意简述** 柏林军队正在准备一场大规模的阅兵式。参加的士兵将被分成人数相等的$k$行。 当然，排兵布阵是需要一定的规则的：同一排士兵的身高相差不应超过$1$且每个士兵的身高是$1$到$n$之间的整数。 已知每名士兵身高的你必须将所有参加阅兵的士兵排成$k$排，以满足上述条件。请你编写程序计算可以参加游行的士兵的最大数量。 **输入格式** 本题**有多组数据**。 第一行包含一个整数$t(1\le t\le 10000)$，表示数据组数。 每组数据都有两行。第一行包含两个整数$n$和$k$（$1≤n≤30000$，$1≤k≤10^{12}$）分别表示不同高度的士兵数量和士兵排数。 第二行包含$n$个整数$c_1,c_2,$ … $,c_n$（$0\le c_i\le 10^{12}$），其中$c_i$表示身高为$i$的士兵人数。 **输出格式** 输出每组数据中可以参加游行的士兵的最大数量。（每两个答案中间有一个换行） **样例说明** 第一组数据，士兵可以站成这样：$[3,3,3,3],[1,2,1,1],[1,1,1,1],[3,3,3,3]$（每个方括号表示一行）； 第二组数据，所有士兵可以全部站成一排； 第三组数据，士兵可以站成$3$排，每排$33$人； 第四组数据，所有士兵可以全部站成一排； 第五组数据，所有身高为$2$和$3$的可以站成一排。

The Berland Army is preparing for a large military parade. It is already decided that the soldiers participating in it will be divided into $ k $ rows, and all rows will contain the same number of soldiers. Of course, not every arrangement of soldiers into $ k $ rows is suitable. Heights of all soldiers in the same row should not differ by more than $ 1 $ . The height of each soldier is an integer between $ 1 $ and $ n $ . For each possible height, you know the number of soldiers having this height. To conduct a parade, you have to choose the soldiers participating in it, and then arrange all of the chosen soldiers into $ k $ rows so that both of the following conditions are met: - each row has the same number of soldiers, - no row contains a pair of soldiers such that their heights differ by $ 2 $ or more. Calculate the maximum number of soldiers who can participate in the parade.

The first line contains one integer $ t $ ( $ 1 \le t \le 10000 $ ) — the number of test cases. Then the test cases follow. Each test case begins with a line containing two integers $ n $ and $ k $ ( $ 1 \le n \le 30000 $ , $ 1 \le k \le 10^{12} $ ) — the number of different heights of soldiers and the number of rows of soldiers in the parade, respectively. The second (and final) line of each test case contains $ n $ integers $ c_1 $ , $ c_2 $ , ..., $ c_n $ ( $ 0 \le c_i \le 10^{12} $ ), where $ c_i $ is the number of soldiers having height $ i $ in the Berland Army. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 30000 $ .

For each test case, print one integer — the maximum number of soldiers that can participate in the parade.

5
3 4
7 1 13
1 1
100
1 3
100
2 1
1000000000000 1000000000000
4 1
10 2 11 1

16
100
99
2000000000000
13

Explanations for the example test cases: 1. the heights of soldiers in the rows can be: $ [3, 3, 3, 3] $ , $ [1, 2, 1, 1] $ , $ [1, 1, 1, 1] $ , $ [3, 3, 3, 3] $ (each list represents a row); 2. all soldiers can march in the same row; 3. $ 33 $ soldiers with height $ 1 $ in each of $ 3 $ rows; 4. all soldiers can march in the same row; 5. all soldiers with height $ 2 $ and $ 3 $ can march in the same row.