시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB36262571.429%

문제

You have successfully led a group of pirates in taking over a commercial vessel. You have seized gold coins, silver coins, and other precious goods. Now it comes down to dividing the loot. It is important to keep everyone satisfied, otherwise you risk mutiny. A pirate is not satisfied if another pirate gets more items than he does. Therefore you might have to content yourself with fewer items than the other pirates or throw some items into open sea. Fortunately, the other pirates have no notion of the value of the items, while you do. Can you make the most out of this without mutiny?

입력

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

  • One line with two integers P and N, satisfying 0 ≤ P ≤ 1000, 1 ≤ N ≤ 1000: the number of other pirates you have to share the loot with and the number of items, respectively.
  • One line with N integers, vi, satisfying 1 ≤ vi ≤ 1000: the value of each item.

출력

For every test case in the input, the output should contain one integer on a single line: the maximum total value of all the items that you can give yourself, while keeping all other pirates satisfied.

예제 입력 1

2
2 7
1 1 1 1 3 3 7
5 9
2 2 4 4 6 8 11 11 13

예제 출력 1

10
13