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 array is : [ 3 4 5 5 8] answer is : 9

how to solve? i didn’t figure out.