Банковское дело
Молодой ломбардец Гуччо Бальйони (герой серии произведений французского писателя Мориса Дрюона) часто выполнял тайные поручения современных ему власть предержащих Франции, Англии и Италии. Не имея возможности в течение трех лет непосредственно самому заниматься делами, он решил извлечь выгоду, вложив деньги в дела парижских банкиров. Оказалось, что размер вознаграждения (% выгоды) разный у разных банкиров. Конечно, чем большую сумму он даст банкирам, тем большую сумму получит через 3 года. И конечно же не меньше, чем дал банкиру. Но у каждого банкира % выгоды разные для разных сумм. К сожалению, по расчетам Гуччо, ему никогда не получить больше 1000 ливров (средневековых французских монет).
Помогите молодому ломбардцу получить наибольшую прибыль.
Входные данные
Первая строка содержит количество ливров m (1 ≤ m ≤ 100), которое молодой Гуччо может использовать для обогащения и количество парижских банкиров n (1 ≤ n ≤ 100).
Для j в границах от 1 до m (j + 1)-ая строка содержит последовательность n натуральных чисел. k-ый член этой последовательности - это количество монет, которое получит Гуччо через три года от k-го банкира, отдав ему j монет перед отъездом.
Выходные данные
Первая строка должна содержать наибольшее количество ливров, которыми может обладать молодой ломбардец через 3 года, использовав m ливров должным образом.
Вторая строка должна содержать последовательность n неотрицательных целых чисел. k-ый член этой последовательности - это количество ливров, которое должен дать Гуччо k-му банкиру, чтобы получить максимальную прибыль от своих капиталовложений (следует вывести хотя бы один из вариантов распределения).