Вы успешно возглавил группу пиратов при нападении на коммерческое судно. Вы захватили золотые и серебряные монеты, а также другие ценные товары.. Теперь пришло время делить награбленное. Очень важно, чтобы каждый пират был удовлетворен, иначе появится риск мятежа. Пират будет не удовлетворен, если другой пират получит больше предметов, чем он. Поэтому Вам возможно придется довольствоваться меньшим количеством предметов, чем другие пираты, либо выбросить некоторые вещи в открытое море. К счастью, другие пираты не имеют понятия о ценности предметов, в то время как у Вас такая информация есть. Сможете ли Вы разделить большую часть имеющихся предметов без мятежа?
Первая строка содержит количество тестов. Каждый тест имеет следующий формат:
одна строка, содержащая два целых числа p и n (0 ≤ p ≤ 1000, 1 ≤ n ≤ 1000) - количество пиратов, с которыми Вам следует поделиться награбленным, и количество предметов.
одна строка с n целыми числами v_i (1 ≤ v_i ≤ 1000) - стоимости каждого предмета.
Для каждого теста вывести в одной строке наибольшую возможную ценность предметов, которую Вы сможете оставить себе, удовлетворив при этом всех пиратов.