\begin{tutorial}{Черепашка наносит ответный удар}

Для $n, m \le 100$ можно написать переборное решение: перебираем, какую клетку выберет Рафаэль, и для каждого варианта считаем, сколько удовольствия получит Микеланджело. Это считается простейшей \emph{динамикой-черепашкой}.

Для дальнейших решений выделим один из путей $S$ из $(1, 1)$ в $(n, m)$, который на исходной пицце доставляет Микеланджело максимальное удовольствие. Клетки этого пути назовём $s_1, s_2, \ldots, s_{n + m - 1}$. Заметим, что если Рафаэль не выберет ни одну из этих клеток, то Микеланджело выберет путь $S$ и получит максимально возможное удовольствие (благодаря неотрицательным по удовольствию кускам пиццы Рафаэль всегда может сделать ход, который не увеличит доступное Микеланджело удовольствие). А значит, если Рафаэль претендует на что-то большее, он должен заблокировать одну из клеток $s_1, \ldots, s_{n + m - 1}$.

Уже из одного этого замечания мы получаем решение за $\mathcal{O}(nm(n + m))$: давайте переберём клетку на пути, которую выберет Рафаэль, и для каждого из этих вариантов снова посчитаем ответ.

Для дальнейших продвижений заметим, что после блокировки клетки $(i, j)$ у Микеланджело будет два варианта: получить на $2 a_{i,j}$ меньше удовольствия, чем максимум, то есть $maxS - 2 a_{i,j}$, или пройти из $(1, 1)$ в $(n, m)$, не посетив клетку $(i, j)$. Первый вариант не требует дополнительных вычислений, а вот второй создаёт некоторые сложности. Давайте разберёмся с ними.

Для клетки $(i, j)$, чтобы гарантировать, что путь не пройдёт через неё, достаточно показать, что на пути будет лежать клетка $(a, b)$, для которой выполняется либо $a < i$ и $b > j$, либо $a > i$ и $b < j$. Отсюда появляется новое решение с той же асимптотикой, но которое уже можно будет оптимизировать: давайте переберём все клетки $(a, b)$ и для каждой клетки $s_k$ сохраним возможность обойти её за
$dpS[a][b] + dpT[a][b] - a[a][b]$,
где $dpS$ и $dpT$~--- вспомогательные динамики, выдающие максимальное удовольствие при движении из $(1, 1)$ в $(a, b)$ и из $(a, b)$ в $(n, m)$ соответственно. По всем таким вариантам для каждой $s_k$ нам нужно сохранить максимум; назовём его $dp[k]$. Тогда ответ формируется как
$\min_k \left( \max\bigl(dp[k],\; maxS - 2 a[s_k]\bigr) \right)$.

Теперь давайте оптимизируем и это решение. Заметим, что нам не нужно перебирать всевозможные клетки $(a, b)$, через которые можно обойти клетку $(i, j)$. Достаточно рассмотреть лишь клетки $(i + 1, q < j)$ и клетки $(p < i, j + 1)$. К сожалению, напрямую перебирать все такие клетки всё ещё долго. Однако заметим, что нам нужно уметь считать
$\max \bigl(dpS[x][y] + dpT[x][y] - a[x][y]\bigr)$
для префиксов точек по $x$ в конкретном столбце и по $y$ в конкретной строке, а именно для наборов
$(i + 1, 1), (i + 1, 2), \ldots, (i + 1, j - 1)$
и
$(1, j + 1), (2, j + 1), \ldots, (i - 1, j + 1)$.

Значения таких префиксных максимумов можно предподсчитать. Таким образом, за $\mathcal{O}(nm)$ предподсчёта мы получаем возможность для каждой клетки $(i, j)$ узнавать максимальное удовольствие маршрута, который не будет посещать её, за $\mathcal{O}(1)$. Итоговая асимптотика решения составляет
$\mathcal{O}(nm + (n + m)) = O(nm)$.

Отметим также, что значительное количество баллов могло набирать решение за $\mathcal{O}(nm \log(nm))$, которое оптимизирует второе решение за $\mathcal{O}(nm(n + m))$ при помощи структур данных.


\end{tutorial}
