예를 들어 , 다음과 같은 수열이 주어질 때

2 5 1 3 3 7

다음과 같이 합 7 로 그룹핑 할 수 있다.

(2 5) (1 3 3) (7)

주의: 한 그룹으로 묶는 것은 전체 수의 합과 같고 이 문제에서는 가장 작은 수의 합으로 묶을 경우 합을 출력한다.

입력

각 데이터 세트의 첫 번째 줄은 데이터 세트의 번호 와 수열의 수 M ( 1 <= M <= 10000) 이 주어진다. 각 줄당 수 는 10 개씩 주어지고 , 마지막 줄은 10 개 보다 적다.

출력

입출력 예

입력

3
1 6
2 5 1 3 3 7
2 6
1 2 3 4 5 6
3 20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

출력

1 7
2 21
3 2

출처:Greater new york 2010