SUSTech Online Judge

Problem 1479 --Split Sticks

1479: Split Sticks

Time Limit: 2 Sec Memory Limit: 512 MB
Submit: 70 Solved: 20
[Submit][Status][Web Board]

Description

Alice has a bundle of sticks. She wants to select some sticks and split them into \(k\) rows.
For beauty, the difference between the lengths of all sticks in the same row shall not exceed 1 and each row has the same number of sticks. The length of each stick is a positive integer from 1 to \(n\).
For every possible length, you know the amount of stick with that length.
Please calculate the maximum number of sticks Alice can select.

Input

The 1st line is a positive integer \(T(1⩽ T ⩽ 10000)\)which is the number of test cases.
For each test case:
The first line contains two integers \(n(1⩽ n ⩽ 30000)\) and \(k(1⩽ k ⩽ 10^{12})\), representing the number of different length of sticks and the number of rows the stick needs to be divided into, respectively
The second line contains n integers \(C_1, C_2 ... C_n\) \((0⩽ C_i ⩽ 10^{12})\)), representing the number of sticks in each length
Ensure that the sum of n of all cases does not exceed 30000

Output

For each case, output the maximum number of sticks Alice can select.

Sample Input

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

Sample Output

16
100
99
2000000000000
13

HINT

1. The arrangement is [3,3,3,3], [1,2,1,1], [1,1,1,1], [3,3,3,3](each list represents a row)

2. All the sticks can be arranged in the same row

3. 33 sticks with length 1 in each 3 rows

4. All the sticks can be arranged in the same row

5. All sticks with lengths of 2 and 3 are arranged in the same row

Source

[Submit][Status]