Поділ награбованого
Ви успішно очолили групу піратів під час нападу на комерційне судно. Ви захопили золоті та срібні монети, а також інші цінні товари. Тепер настав час ділити награбоване. Дуже важливо, щоб кожен пірат був задоволений, інакше з'явиться ризик бунту. Пірат буде незадоволений, якщо інший пірат отримає більше предметів, ніж він. Тому вам, можливо, доведеться задовольнятися меншою кількістю предметів, ніж інші пірати, або викинути деякі речі у відкрите море. На щастя, інші пірати не мають уявлення про цінність предметів, тоді як у вас така інформація є. Чи зможете ви розділити більшу частину наявних предметів без бунту?
Вхідні дані
Перша строка містить кількість тестів.
Перша строка кожного тесту містить два цілих числа p і n (0 ≤ p ≤ 1000, 1 ≤ n ≤ 1000) - кількість піратів, з якими вам слід поділитися награбованим, і кількість предметів. Друга строка тесту містить n цілих чисел v[i] (1 ≤ v[i] ≤ 1000) - вартості кожного предмета.
Вихідні дані
Для кожного тесту виведіть в одному рядку найбільшу можливу цінність предметів, яку ви зможете залишити собі, задовольнивши при цьому всіх піратів.