Homework#5479
Petro does not like doing homework, so he asks the top students in his class to do it for him, offering them chocolate candies in return. Since Petro's father works at a chocolate factory, he always has enough candies. However, the top students are particular: on different days, they may demand a different number of candies for completing the homework. In addition, each top student is only willing to do Petro's homework for a limited number of consecutive days.
For every top student in the class, Petro knows:
The maximum number of consecutive days this student is willing to do his homework.
For each day, the number of candies that student demands to do the homework for that day.
Given this information, determine the minimum total number of candies Petro must give to top students so that his homework is done every day, and for each day assign a top student to do the work.
The first line contains two integers: — the number of consecutive school days Petro needs his homework completed, and — the number of top students in his class (1 \leq n \leq 100, 2 \leq m \leq 100).
The second line contains integers a_i (1 \leq i \leq m), where a_i is the maximum number of consecutive assignments the -th top student is willing to do for Petro (1 \leq a_i \leq n).
The following lines each contain non-negative integers. The -th number in the -th line denotes the number of candies Petro must give to the -th top student to do his homework on the -th day. All these numbers do not exceed 10^6. Numbers in each line are separated by spaces.
Print in the first line a single integer — the minimum number of candies required.
In the second line, print integers, each indicating the index of the top student who should do Petro's homework on the corresponding day (indices are from to ).
Example 1