Задача 1 из 21

Груз на космодроме

Время 2 с · память 256 МБ

На космодроме находятся NN контейнеров одинаковых габаритов, которые нужно перевезти на грузовом космическом корабле. Общая масса контейнеров превышает грузоподъёмность корабля SS, а количество грузовых мест на корабле не меньше числа контейнеров.

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

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

В первой строке находятся два натуральных числа: SS — грузоподъёмность корабля (S≤100 000S \le 100\,000) и NN — количество контейнеров (N≤10 000N \le 10\,000). В каждой из следующих NN строк находится масса одного контейнера — натуральное число, не превышающее 100.

Массы идут в произвольном порядке и могут повторяться. Гарантируется, что их сумма больше SS.

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

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

Примеры

Ввод 1
100 4
80
30
50
40
Вывод 1
2 130
Ввод 2
1 1
2
Вывод 2
1 2

Примечание

В первом примере можно перевезти два контейнера массами 30 и 40. На космодроме останутся 50 и 80: два контейнера суммарной массой 130. Во втором примере единственный контейнер слишком тяжёлый, поэтому остаётся один контейнер массой 2.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче