Подпроекты

Рамзи Сарнаех создал новую компанию пригородных услуг, которую назвал Нерешенные Идеи (НИ). Пока Рамзи в НИ еще не нанял работников, поэтому он первые несколько месяцев должен работать сам, пока он не сможет расширить свою компанию. Недавно он получил некоторые проекты от правительственных министерств и разбил все проекты на меньшие независимые подпроекты с разными стоимостями. Мы предполагаем, что все подпроекты могут быть выполнены за единицу времени. Рамзи, имея ограниченное время, но будучи оптимистом, хочет знать, сколько, в наилучшем случае, он может заработать, принимая более ценные подпроекты и отклоняя другие.

Технические условия

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

В первой строке целое число – количество тестовых случаев. Далее идут данные, размещенные в одной строке для каждого тестового случая. Каждый тестовый случай начинается с двух целых чисел: времени, имеющегося в распоряжении Рамзи (T) и количество подпроектов (P), соответственно (0 ≤ T, P ≤ 1000). После этих двух чисел идет P неотрицательных целых чисел (от 0 до 32767, включительно), которые являются значениями стоимости подпроектов. Все числа в тестовых случаях разделены пробелом.

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

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 10% 203/225
Мои результаты: 0/1

Пример

Пример входных данных

3
3 5 1 1 1 1 1
4 2 161 5
4 7 8 2 9 17 4 4 10

Пример выходных данных

3
166
44

← Лист бумаги

Список задач