Problem :

This is the time of Christmas and Santa wants to distribute gifts to M children. He has N number of boxes, and each box contains some chocolates. Now, Santa wants to distribute N boxes to M children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, Santa wants to minimize the maximum number of choclates gifted to a child.

Formally, given M number of children and N boxes, where each box contains some amount of chocolates. The task is to minimize the maximum number of chocolate gifted to a child.

In another word, you have to divide array into M subset such that maximum sum of subset is minimized.

Input:

First line of input contains number of testcases T. For each testcase, there will be three lines of input. First line contains N number of gift boxes, next line contains choclates in each of the N boxes. Last line contains number of children.

Output:

For each testcase, print the minimum number of maximum chocolate a child get.

Constraints:

1 <= T <= 100

1 <= N, M <= 10^6

1 <= A[i] <= 10^8

Example:

Input:

1

4

12 34 67 200

3

Output:

200

Explanation:

Testcase 1: Minimum 200 chocolates will be given to a child which gets the maximum number of chocolate.

Another Corner Case : n = 5 and m=3

array is : [ 3 4 5 5 8]

answer is : 9

how to solve? i didnâ€™t figure out.