13373번 - Rearrange 다국어

The code for getMin( ) function is shown below. Given an integer n and an array of integers arr, you have to write the rearrange( ) function which will be called by the getMin( ) function so that your rearrange( ) function minimize the return value from the getMin( ) function.

int getMin(int n, int arr[]){
    arr2 = rearrange(arr);
    for(int i = 0; i < arr2.length(); i = i+1){
        n = n-arr2[i];
        if (n <= 0) break;
    }
    return n;
}

Your rearrange( ) function should get an array of integers as an input and then return a new array of integers. The new array must contain the same members of the old array but the position of each member may be changed.

In this contest, the judges do not care about how you code the rearrange( ) function. You just have to submit the minimum return value of thegetMin( ) function to win the contest.

The first line will contain the number of test cases T. (1 ≤ T ≤ 10)

For each test case, there will be 2 lines. The first line of each test case contains 2 integers, n (0 ≤ n ≤ 10 000) and k (0 ≤ k ≤ 10 000), the length of array arr. The second line contains the members of array arr, arr[0], ... , arr[k-1] (0 ≤ arr[i] ≤ 1 000 000). There will be exactly k integers in this line. Each integer is separated with a space.

For each test case, print the minimum return value from getMin( ) function, one test case per line.

Explanation for sample test case 2: you send [70, 60, 80] to the rearrange( ) function and it returns [80, 70, 60]. There can be more than one ways to rearrange the array arr in order to minimize the getMin( ) function’s return value.