3.2 Aircrafts

Score: 30pts

Time Limit: 5.00 sec

You are provided a list of numbers nums of length n, where each value denotes a group of individuals interested in tandem skydiving. Additionally, k, the number of days the skydiving facility is open, is provided.

Return the bare minimum number of aircraft capacity needed to complete all requests in k days. Requirements must be fulfilled in the order they were obtained, and a plane can only take off once per day.

Return the bare minimum number of aircraft capacity needed to complete all requests in k days. Requirements must be fulfilled in the order they were obtained, and a plane can only take off once per day.

Constraints

1 <= t <= 10

1 <= n <= 10000

1<= nums[i] <= 10000

1 <= k <= n

1 <= n <= 10000

1<= nums[i] <= 10000

1 <= k <= n

Input Format

The first line contains the number of test cases t

For each test case then:

The first line contains the number of numbers i.e. n

The second line contains the numbers themselves i.e. nums

The third line contains the number of days the skydiving facility is open i.e. k

For each test case then:

The first line contains the number of numbers i.e. n

The second line contains the numbers themselves i.e. nums

The third line contains the number of days the skydiving facility is open i.e. k

Output Format

The minimum capacity of the airplane needed to efficiently accommodate all the groups on the given days

Example 1

Input:

1

5

13 17 30 15 17

3

Output:

32

Explanation:

A 32 person airplane can group the requests by [13, 17], [30], [15, 17]

1

5

13 17 30 15 17

3

Output:

32

Explanation:

A 32 person airplane can group the requests by [13, 17], [30], [15, 17]