| Автор: | Г. Гренкин, А. Кленин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt |
Однажды Чудик попал в загадочную страну Цветландию. Эта страна имеет форму квадрата, разделённого на N × N маленьких квадратиков — регионов.
В каждом регионе растут цветы определённого сорта. У цветов каждого сорта есть определённый период цветения T. Цветы растут T дней, после чего увядают и начинают расти заново.
Цветы каждого региона в каждый из дней имеют определённую силу запаха, В первый день роста цветы не пахнут (сила запаха равна нулю), затем сила запаха увеличивается на единицу каждый день, вплоть до дня увядания. Таким образом, цветы с периодом цветения T в k-й день имеют силу запаха (k−1) mod T.
Чудик очень любит нюхать цветы, поэтому он хочет выбрать свой маршрут путешествия по Цветландии так, чтобы как можно сильнее ощутить запах цветов.
Чудик выбирает, с какого региона он начнёт путешествие, и отправляется в путь. Путешествие Чудика длится K дней. За один день Чудик должен переместиться в соседний (сверху, справа, снизу или слева) регион.
В k-й день путешествия Чудика в регионе с координатами (x, y) цветы имеют силу запаха (k−1) mod T(x, y), где T(x, y) — период цветения цветов этого региона.
Чудик хочет выбрать маршрут так, чтобы сумма сил запаха в регионах, через которые он пройдёт, была максимальной.
Комментарий к примеру
Силы запаха в регионах по дням:
| 1 | 2 | 3 | 4 |
0 0 0 0 |
1 1 1 1 |
0 0 2 0 |
1 1 0 1 |
Входной файл содержит целые числа N K. Далее следуют N2 целых чисел T(x, y).
Выходной файл должен содержать целое число — максимальную сумму сил запаха.
2 ≤ N ≤ 100
1 ≤ K ≤ 100
2 ≤ T(x, y) ≤ 100
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|