In connection with the approaching end of the coronavirus epidemic, the government of the city of Ensk decided to send excellent students of the city's schools - N vacationers to the southern sea resorts.
Airlines have K types of aircraft for transportation with different numbers of passenger seats (P
1, P
2,...,P
k). It is necessary to solve the logistical problem: reserve the required number of flights (R
1, R
2,...,R
k).
The total number of seats cannot be less than the number of passengers, and the total number of unoccupied passenger seats (V) must be minimal. If several options are found that are identical in terms of the number of unoccupied seats, then you should choose the option with a smaller total number of aircraft flights. If there are several such options, then you need to display any of them.
Input
the first line contains 2 natural numbers N and K separated by a space, the second line contains K natural numbers P
1 P
2 … P
k. N does not exceed 10000, K does not exceed 20, any P
i is less than 500.
Imprint
in the first line print the number V, in the second line print R
1 R
2 … R
k. The order of the number of flights must match the original order of the aircraft types.
Examples
| # |
Input |
Output |
| 1 |
1000 3
300 220 150
| 30 0
0 4 1
|
| 2 |
80 4
100 50 40 30
| 0
0 1 0 1 (option - 0 0 2 0) |