재배치

아래는 getMin( ) 함수의 코드다.

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;
}

getMin( )은 정수 $n$과 정수 배열 arr를 받아 rearrange( )를 호출한다. rearrange( )는 정수 배열을 받아 새 배열을 돌려준다. 새 배열의 원소는 원래 배열의 원소와 같고, 각 원소의 위치는 바뀔 수 있다.

rearrange( )를 어떻게 구현하는지는 채점하지 않는다. getMin( )의 반환값을 가장 작게 만드는 배치를 골랐을 때 그 반환값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스는 두 줄이다. 첫 줄에는 정수 $n$과 배열 arr의 길이 $k$가 공백으로 구분되어 주어진다. ($0 \le n \le 10000$, $0 \le k \le 10000$) 둘째 줄에는 arr[0]부터 arr[k-1]까지 정수 $k$개가 공백으로 구분되어 주어진다. ($0 \le \texttt{arr}[i] \le 1000000$) $k$가 $0$이면 둘째 줄은 빈 줄이다.

각 테스트 케이스마다 getMin( )이 돌려줄 수 있는 최솟값을 한 줄에 하나씩 출력한다. 값은 음수일 수 있다.

예제의 둘째 테스트 케이스에서 rearrange( )에 [70, 60, 80]을 넘기고 [80, 70, 60]을 돌려받으면 $100 - 80 = 20$이고 $20 - 70 = -50$이라 반복문이 멈춰 $-50$을 반환한다. 반환값을 최소로 만드는 배치는 여러 가지일 수 있지만, 출력하는 값은 그 최솟값 하나다.