Задача 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 парна.