Задача Oddsum
Дана прямоугольная таблица размером N строк на M столбцов; в каждой клетке записано целое число. По ней нужно пройти сверху вниз, начав путь в какой-нибудь клетке верхней строки, далее каждый раз переходя в одну из «нижне-соседних» клеток (иными словами, из клетки с номером (i, j) можно перейти либо в (i+1, j–1), либо в (i+1, j), либо в (i+1, j+1); в случае j=M возможны только 1-й и 2-й из трех перечисленных вариантов, в случае j=1 — только 2-й и 3-й) и закончив путь в какой-нибудь клетке нижней строки. Напишите программу, находящую максимально возможную нечетную сумму значений пройденных клеток (среди всех допустимых путей).
При этом отдельные числа могут быть четными; нечетной должна получиться окончательная сумма.
Технические условия Программа Oddsum читает с клавиатуры N и M — количество строк и количество столбцов (2≤M≤500, 2≤N≤500), а далее - N строк из M разделенных пробелами целых чисел (каждое не превосходит по модулю 1 000 000) — значения клеток таблицы. Программа выводит на экран единственное целое число — найденную максимально возможную нечетную сумму. Если сформировать нечетную сумму вообще невозможно, программа должна вместо ответа вывести -2.
Пример
|
Ввод |
Вывод |
|
4 3 1 15 2 9 7 5 9 2 4 6 9 –1 |
39 |
Примечание к примеру
Наилучший (з суммой 39) допустимый путь проходит через клетки со значениями 15, 9, 9, 6. Путь, проходящий через клетки со значениями 15, 9, 9, 9, имеет еще большую сумму 42, но для данной задачи он не допустимый, так как сумма 42 четна.