eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дележ награбленного

Дележ награбленного

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
prb3118

Вы успешно возглавили группу пиратов при нападении на коммерческое судно. Вы захватили золотые и серебряные монеты, а также другие ценные товары. Теперь пришло время делить награбленное. Очень важно, чтобы каждый пират был удовлетворен, иначе появится риск мятежа. Пират будет не удовлетворен, если другой пират получит больше предметов, чем он. Поэтому Вам возможно придется довольствоваться меньшим количеством предметов, чем другие пираты, либо выбросить некоторые вещи в открытое море. К счастью, другие пираты не имеют понятия о ценности предметов, в то время как у Вас такая информация есть. Сможете ли Вы разделить большую часть имеющихся предметов без мятежа?

Входные данные

Первая строка содержит количество тестов.

Первая строка каждого теста содержит два целых числа p и n (0p1000, 1n1000) - количество пиратов, с которыми Вам следует поделиться награбленным, и количество предметов. Вторая строка теста содержит n целых чисел v[i] (1v[i]1000) - стоимости каждого предмета.

Выходные данные

Для каждого теста вывести в одной строке наибольшую возможную ценность предметов, которую Вы сможете оставить себе, удовлетворив при этом всех пиратов.

Пример

Входные данные #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
Источник 2011 Benelux Algorithm Programming Contest, Preliminaries, Задача F