Домашні завдання#5479
Петро дуже не любить робити домашні завдання, тому просить відмінників зі свого класу зробити їх за нього, пропонуючи взамін шоколадні цукерки. Оскільки батько Петра працює на шоколадній фабриці, у Петра завжди достатньо цукерок. Проте відмінники вимогливі: у різні дні вони просять різну кількість цукерок за виконання домашнього завдання. Крім того, кожен відмінник погоджується виконувати домашнє завдання за Петра лише обмежену кількість днів поспіль.
Для кожного відмінника у класі Петро знає:
Максимальну кількість днів поспіль, яку цей відмінник готовий виконувати за нього домашні завдання.
Для кожного дня — кількість цукерок, яку цей відмінник вимагатиме за виконання завдання.
Потрібно визначити мінімальну кількість цукерок, яку Петро повинен віддати відмінникам, щоб кожного дня домашнє завдання було виконано, а також для кожного дня вказати відмінника, який буде виконувати завдання цього дня.
Перший рядок містить два числа: — кількість навчальних днів поспіль, протягом яких Петру потрібно, щоб його домашні завдання виконували відмінники, та — кількість відмінників у класі (1 \leq n \leq 100, 2 \leq m \leq 100).
Другий рядок містить цілих чисел a_i (1 \leq i \leq m), де a_i — максимальна кількість поспіль виконаних завдань, які -й відмінник погоджується виконати за Петра (1 \leq a_i \leq n).
Наступні рядків містять по невід'ємних цілих чисел. -е число у -му рядку — це кількість цукерок, яку Петро повинен віддати -му відміннику за виконання завдання у -й день. Всі ці числа не перевищують 10^6. Числа в рядках відокремлюються пропусками.
У першому рядку виведіть одне число — мінімальну кількість цукерок, яка потрібна Петру. У другому рядку виведіть цілих чисел: для кожного дня — номер відмінника, який у цей день виконує завдання за Петра (номери від до ).
Приклад 1