В связи с приближающимся завершением эпидемии коронавируса правительство города Энска приняло решение отправить на южные морские курорты отличников школ города - N отдыхающих.
В авиакомпаниях для перевозки имеются K типов самолётов с различным количеством пассажирских мест (P
1, P
2,...,P
k). Необходимо решить логистическую задачу: зарезервировать необходимое количество рейсов (R
1, R
2,...,R
k).
Суммарное количество посадочных мест не может быть меньше, чем количество пассажиров, а общее количество незанятых пассажирских мест (V) должно быть минимальным. Если будет обнаружено несколько вариантов, одинаковых по количеству незанятых мест, то следует выбрать вариант с меньшим общим количеством рейсов самолётов. Если и таких вариантов будет несколько, то нужно вывести любой из них.
Входные данные
в первой строке через пробел записаны 2 натуральных числа N и K, во второй - K натуральных чисел P
1 P
2 … P
k. N не превышает 10000, K не превышает 20, любое P
i меньше 500.
Выходные данные
в первой строке вывести число V, во второй через пробел вывести R
1 R
2 … R
k. Порядок количеств рейсов должен соответствовать исходному порядку типов самолётов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1000 3
300 220 150 |
30 0
0 4 1 |
| 2 |
80 4
100 50 40 30 |
0
0 1 0 1 (вариант - 0 0 2 0) |