eolymp
bolt
Try our new interface for solving problems
Problems

Банковское дело

Банковское дело

Time limit 1 second
Memory limit 64 MiB

Молодой ломбардец Гуччо Бальйони (герой серии произведений французского писателя Мориса Дрюона) часто выполнял тайные поручения современных ему власть предержащих Франции, Англии и Италии. Не имея возможности в течение трех лет непосредственно самому заниматься делами, он решил извлечь выгоду, вложив деньги в дела парижских банкиров. Оказалось, что размер вознаграждения (% выгоды) разный у разных банкиров. Конечно, чем большую сумму он даст банкирам, тем большую сумму получит через 3 года. И конечно же не меньше, чем дал банкиру. Но у каждого банкира % выгоды разные для разных сумм. К сожалению, по расчетам Гуччо, ему никогда не получить больше 1000 ливров (средневековых французских монет).

Помогите молодому ломбардцу получить наибольшую прибыль.

Input data

Первая строка содержит количество ливров m (1m100), которое молодой Гуччо может использовать для обогащения и количество парижских банкиров n (1n100).

Для j в границах от 1 до m (j + 1)-ая строка содержит последовательность n натуральных чисел. k-ый член этой последовательности - это количество монет, которое получит Гуччо через три года от k-го банкира, отдав ему j монет перед отъездом.

Output data

Первая строка должна содержать наибольшее количество ливров, которыми может обладать молодой ломбардец через 3 года, использовав m ливров должным образом.

Вторая строка должна содержать последовательность n неотрицательных целых чисел. k-ый член этой последовательности - это количество ливров, которое должен дать Гуччо k-му банкиру, чтобы получить максимальную прибыль от своих капиталовложений (следует вывести хотя бы один из вариантов распределения).

Examples

Input example #1
3 10
1 1 6 2 2 5 2 1 3 3
2 4 7 8 3 7 8 4 8 5
7 10 12 10 4 9 11 6 13 7
Output example #1
14
0 0 1 2 0 0 0 0 0 0