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.
输入输出样例
输入样例 #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
说明
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.