Задача B. Чудик в Цветландии ≡

Условие

Однажды Чудик попал в загадочную страну Цветландию. Эта страна имеет форму квадрата, разделённого на N × N маленьких квадратиков — регионов.

В каждом регионе растут цветы определённого сорта. У цветов каждого сорта есть определённый период цветения T. Цветы растут T дней, после чего увядают и начинают расти заново.

Цветы каждого региона в каждый из дней имеют определённую силу запаха, В первый день роста цветы не пахнут (сила запаха равна нулю), затем сила запаха увеличивается на единицу каждый день, вплоть до дня увядания. Таким образом, цветы с периодом цветения T в k-й день имеют силу запаха (k − 1) mod T.

Чудик очень любит нюхать цветы, поэтому он хочет выбрать свой маршрут путешествия по Цветландии так, чтобы как можно сильнее ощутить запах цветов.

Чудик выбирает, с какого региона он начнёт путешествие, и отправляется в путь. Путешествие Чудика длится K дней. За один день Чудик должен переместиться в соседний (сверху, справа, снизу или слева) регион.

В k-й день путешествия Чудика в регионе с координатами (x, y) цветы имеют силу запаха (k − 1) mod T(x, y), где T(x, y) — период цветения цветов этого региона.

Чудик хочет выбрать маршрут так, чтобы сумма сил запаха в регионах, через которые он пройдёт, была максимальной.

Комментарий к примеру

Силы запаха в регионах по дням:

0 0
0 0

1 1
1 1

0 0
2 0

1 1
0 1

Формат входного файла

Входной файл содержит целые числа N K. Далее следуют N² целых чисел T(x, y).

Формат выходного файла

Выходной файл должен содержать целое число — максимальную сумму сил запаха.

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 100

2 ≤ T(x, y) ≤ 100

Примеры тестов

2 4
2 2
3 2

4

Разбор

Применим метод динамического программирования, который заключается в следующем. Исходная задача разбивается на подзадачи. Затем выводится рекуррентное соотношение, связывающее решение большей подзадачи с решениями меньших подзадач. Рекуррентное соотношение позволяет вычислить решение большей подзадачи, если решения меньших подзадач уже вычислены. Подзадачи решаются от меньших к бОльшим, и в конечном итоге мы приходим к решению исходной задачи.

Подзадача: найти максимальную сумму сил запаха, если прошло k дней и на k-й день Чудик оказался в регионе с координатами (x, y).

Пусть f(x, y, k) — решение такой подзадачи.

Пусть a(x, y, k) — сила запаха в регионе с координатами (x, y) в k-й день: a(x, y, k) = (k − 1)mod T(x, y).

f(x, y, 1) = a(x, y, 1) = 0.

Рекуррентное соотношение: f(x, y, k) = a(x, y, k) + max(f(x − 1, y, k − 1), f(x + 1, y, k − 1), f(x, y − 1, k − 1), f(x, y + 1, k − 1)).

Решение исходной задачи: max f(x, y, K), где максимум берётся по всем x, y от 1 до N.