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. Explanations for the example test cases: 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); all soldiers can march in the same row; (33) soldiers with height (1) in each of (3) rows; a