Задача №114892. Марио и параллельный мир
Однажды Марио и Луиджи переместились в параллельный мир. Он представляет собой матрицу из n строк и m столбцов, в каждой ячейке которой записано целое положительное число. Цель Марио в этом мире — дойти из верхнего левого угла в правый нижний, получив как можно больше очков. За один шаг Марио может перемещаться в соседнюю по стороне клетку справа или снизу от его текущего положения, если эта клетка существует.
Очки Марио за его маршрут равны сумме чисел в посещённых клетках. Луиджи недавно поссорился с Марио и хочет ему помешать. Он может занять какую-то клетку поля, не совпадающую с верхним левым и правым нижним углом, тогда Марио не сможет проходить через эту клетку. Он хочет занять клетку так, чтобы Марио, выбрав оптимальный для себя в новых условиях маршрут, получил как можно меньше очков.
Найдите число очков, которое получит Марио, выбрав оптимальный маршрут, если Луиджи будет действовать так, чтобы сделать результат Марио как можно хуже. Гарантируется, что какую бы клетку не занял Луиджи, Марио сможет добраться из левого верхнего угла до правого нижнего.
В первой строке находятся два целых числа n , m — длина и ширина поля соответственно ( 2 ≤ n , m ≤ 1500 ).
В каждой из следующих n строк находятся по m целых чисел, j -е число в i -й строке a i , j является числом, написанным в соответствующей клетке поля ( 1 ≤ a i , j ≤ 10 9 ).
В единственной строке выведите целое число — число очков, которое получит Марио, выбрав оптимальный маршрут, если Луиджи так же будет действовать оптимально.
Эта задача состоит из трех подзадач. Для подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех предыдущих подзадач и тесты из условия.
| Подзадача | Баллы | Ограничения |
| 1 | 29 | 2 ≤ n , m ≤ 100 |
| 2 | 32 | 2 ≤ n , m ≤ 300 |
| 3 | 39 | 2 ≤ n , m ≤ 1500 |
В первом тесте из условия оптимальный ответ будет, если Луиджи займет 3-ю клетку во 2-й строке, тогда Марио сможет набрать не более 17 очков.
4 4 1 2 3 4 2 1 3 1 3 2 3 5 1 3 4 1
17