전리품 나누기

해적 무리를 이끌고 상선을 성공적으로 나포했습니다. 금화와 은화를 비롯한 값진 물건들을 손에 넣었고, 이제 전리품을 나눌 차례입니다. 반란을 피하려면 모두를 만족시키는 것이 중요합니다. 어떤 해적이든 다른 해적이 자기보다 물건을 더 많이 가져가면 불만을 품습니다. 따라서 당신은 다른 해적들보다 물건을 적게 가지거나, 일부 물건을 바다에 던져 버려야 할 수도 있습니다. 다행히 다른 해적들은 물건의 가치를 전혀 모르지만, 당신은 알고 있습니다. 반란을 일으키지 않으면서 최대한 이득을 챙길 수 있을까요?

입력의 첫 줄에는 이어지는 테스트 케이스의 개수를 나타내는 정수 하나가 주어집니다. 각 테스트 케이스는 다음과 같은 형식입니다.

• 첫 줄에는 두 정수 $P$와 $N$이 주어집니다 ($0 \le P \le 1000$, $1 \le N \le 1000$). 각각 당신이 전리품을 함께 나눠야 하는 다른 해적의 수와 물건의 개수를 뜻합니다.
• 둘째 줄에는 $N$개의 정수 $v_i$가 주어집니다 ($1 \le v_i \le 1000$). 각 물건의 가치를 나타냅니다.

각 테스트 케이스마다, 다른 모든 해적을 만족시키면서 당신이 스스로 가져갈 수 있는 물건들의 최대 가치 합을 정수 하나로 한 줄에 출력합니다.