410409: GYM104018 B Ограбление века

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

В городе появились преступники, планирующие ограбить часть домов.

Всего в городе $$$N \times M$$$ домов, расположенных в виде прямоугольной сетки. Каждый дом задаётся двумя целочисленными координатами $$$(i, j)$$$ $$$(1 \le i \le N, 1 \le j \le M)$$$, где $$$(1, 1)$$$ — координаты левого верхнего дома, а $$$(N, M)$$$ — правого нижнего.

В доме с координатами $$$(i,j)$$$ хранятся ценности стоимостью $$$C_{i,j}$$$. Если преступники грабят дом, то они выносят все имеющиеся в нём ценности.

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

Два дома с координатами $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$ являются соседними, если $$$|i_1 - i_2| + |j_1 - j_2| = 1$$$, где $$$|x|$$$ — абсолютное значение числа $$$x$$$.

Найдите максимально возможную суммарную стоимость ценностей, которыми могут овладеть преступники, если выберут оптимальный набор домов для грабежа.

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

В первой строке расположены два целых числа $$$N$$$ и $$$M$$$ $$$(2 \leq N \times M \leq 100)$$$ — размеры города.

В следующих $$$N$$$ строках находятся по $$$M$$$ целых чисел $$$C_{i,j}$$$ $$$(1 \le C_{i,j} \le 10^6; 1 \le i \le N, 1 \le j \le M)$$$ — стоимости ценностей в домах с соответствующими координатами.

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

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

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

4 3
5 4 5
3 5 9
1 2 4
8 9 10

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

36

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

3 3
10 1 1
1 1 1
1 10 1

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

21

Примечание

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

Преступникам оптимально выбрать следующие дома:

• $$$(1, 2)$$$ — стоимость $$$4$$$;
• $$$(2, 1)$$$ — стоимость $$$3$$$;
• $$$(2, 3)$$$ — стоимость $$$2$$$;
• $$$(3, 2)$$$ — стоимость $$$9$$$;
• $$$(4, 1)$$$ — стоимость $$$8$$$;
• $$$(4, 3)$$$ — стоимость $$$10$$$.

Общая суммарная стоимость ценностей в данных домах равна $$$4 + 3 + 2 + 9 + 8 + 10 = \textbf{36}$$$.

Обратите внимание, что преступники не могут взять вместе следующие пары домов:

• $$$(1, 3)$$$ и $$$(2, 3)$$$ — они являются соседними по координате $$$i$$$: $$$|1 - 2| + |3 - 3| = 1$$$;
• $$$(4, 2)$$$ и $$$(4, 3)$$$ — они являются соседними по координате $$$j$$$: $$$|4 - 4| + |2 - 3| = 1$$$.

Второй тестовый пример

Один из оптимальных вариантов выбора домов:

• $$$(1, 1)$$$ — стоимость $$$10$$$;
• $$$(1, 3)$$$ — стоимость $$$1$$$;
• $$$(3, 2)$$$ — стоимость $$$10$$$.

Общая суммарная стоимость ценностей в данных домах равна $$$10 + 1 + 10 = \textbf{21}$$$.

Обратите внимание, что вместо дома $$$(1, 3)$$$ преступники могут ограбить дом $$$(2, 3)$$$ — суммарная стоимость награбленного в таком случае не изменится.