Задача: Перевозки
В связи с приближающимся завершением эпидемии коронавируса правительство города Энска приняло решение отправить на южные морские курорты отличников школ города - N отдыхающих.
В авиакомпаниях для перевозки имеются K типов самолётов с различным количеством пассажирских мест (P1, P2,...,Pk). Необходимо решить логистическую задачу: зарезервировать необходимое количество рейсов (R1, R2,...,Rk).
Суммарное количество посадочных мест не может быть меньше, чем количество пассажиров, а общее количество незанятых пассажирских мест (V) должно быть минимальным. Если будет обнаружено несколько вариантов, одинаковых по количеству незанятых мест, то следует выбрать вариант с меньшим общим количеством рейсов самолётов. Если и таких вариантов будет несколько, то нужно вывести любой из них.
Входные данные
в первой строке через пробел записаны 2 натуральных числа N и K, во второй - K натуральных чисел P1 P2 … Pk. N не превышает 10000, K не превышает 20, любое Pi меньше 500.
Выходные данные
в первой строке вывести число V, во второй через пробел вывести R1 R2 … Rk. Порядок количеств рейсов должен соответствовать исходному порядку типов самолётов.
Примеры
| № |
Входные данные |
Выходные данные |
| 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) |
Ваш ответ: