410409: GYM104018 B Ограбление века
Description
В городе появились преступники, планирующие ограбить часть домов.
Всего в городе $$$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)$$$ — суммарная стоимость награбленного в таком случае не изменится.