eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

MaxSum (непарна сума)

MaxSum (непарна сума)

Є прямокутна таблиця розміром \textbf{N} рядків на \textbf{M} стовбчиків. У кожній клітинці записано ціле число. По ній можна пройти зверху вниз, починаючи з довільної клітинки верхнього рядка, далі кожного разу переходячи в одну з "нижніх сусідніх" клітинок (іншими словами, з клітинки під номером (\textbf{i}, \textbf{j}) можна перейти або на (\textbf{i+1}, \textbf{j-1}), або на (\textbf{i+1}, \textbf{j}), або на (\textbf{i+1}, \textbf{j+1}); у випадку \textbf{j=M} останній з трьох описаних варіантів стає неможливим, а у випадку \textbf{j=1} - перший) і завершити маршрут у якій-небудь клітинці нижнього рядка. Напишіть програму, яка буде знаходити максимально можливу непарну суму значень пройдених клітинок серед усіх допустимих шляхів. Зверніть увагу, що непарною повинна бути саме сума; ніяких обмежень на парність/непарність окремих доданків немає. \InputFile У першому рядку записані \textbf{N} та \textbf{M }- кількість рядків та кількість стовбчиків (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{200}), далі у кожному з наступних \textbf{N} рядків записано рівно \textbf{M} відокремлених пропусками цілих чисел (кожне не перевищує по модулю \textbf{10^6}) - значення клітинок таблиці. \OutputFile Вивести єдине число (знайдену максимальну серед непарних сум), або рядок "\textbf{impossible}" (без лапок, маленькими латинськими буквами). Рядок "\textbf{impossible}" повинен виводитись лише у тому випадку, коли абсолютно усі маршрути вказаного виду мають парні суми. \textbf{Примітка}: Взагалі-то максимально можлива сума - \textbf{42 = 15+9+9+9}, але число \textbf{42} парне. Тому відповіддю буде максимальна серед непарних сума \textbf{39 = 15+9+9+6}, яка досягається по маршруту \textbf{a\[1\]\[2\]}, \textbf{a\[2\]\[1\]}, \textbf{a\[3\]\[1\]}, \textbf{a\[4\]\[1\]}.
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Вихідні дані #1
39
Автор Илья Порублёв
Джерело Летняя школа Севастополь 2013, Волна 1, День 2