408798: GYM103325 B Жадный червячок

B. Жадный червячокограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В саду есть $$$n$$$ рядов для посадки деревьев, в каждом из которых растет по $$$m$$$ яблонь. В сад хочет поселиться червячок Иннокентий, и он ищет лучшее место в саду для этого. Главным показателем при выборе яблони для будущего жилья червячок считает размер яблок, растущих на ней.

Изначально Иннокентий располагается в точке $$$(1, 1)$$$ (левой верхней точке сада). Из-за особенностей рельефа сада он может перемещаться только на соседнее дерево снизу или справа. При этом червячок может видеть размеры яблок только на соседних деревьях с тем, где он сейчас находится. Иннокентий не любит рисковать, и поэтому он переползёт на соседнее дерево только при условии, что яблоки на нём строго больше, чем на том, где он находится сейчас. При этом, если таких деревьев не существует, он поселится на текущем дереве. Иначе он переползёт на случайное из соседних деревьев, удовлетворяющих условиям.

Так как скоро зима, Иннокентий просит Вас помочь определить на каком максимальном количестве деревьев ему понадобиться побывать, чтобы найти себе жильё?

Входные данные

В первой строке даны два числа $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 1000)$$$ — количество рядов в саду и деревьев в каждом из них соответственно.

В следующих $$$n$$$ строках описываются ряды деревьев в саду. Таким образом, в $$$(i + 1)$$$-й строке $$$j$$$-е число описывает размер яблок $$$j$$$-го дерева в $$$i$$$-м ряду $$$a_{i, j}$$$ $$$(1 \le a_{i,j} \le 10^6)$$$.

Выходные данные

В единственной строке выходного файла выведите одно число — максимально возможное количество деревьев, на которых может побывать Иннокентий, прежде чем найдет себе жилье.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text {} \\ \hline 1 & 15 & \ a_{i,j} = i + j - 1 & \text {} \\ \hline 2 & 40 & \ 1 \le n, m \le 13 & \text {} \\ \hline 3 & 45 & \text { Нет дополнительных ограничений } & \text {1, 2}\\ \hline \end{array}$$$$$$

ПримерВходные данные

3 4
2 3 2 2
1 4 2 3
4 5 6 4

Выходные данные

5

Примечание

Тесты к этой задаче состоят из 3 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.