MaxSum (tək cəmi)
Düzbucaqlı bir cədvəl verilib, ölçüləri N sətir və M sütundur. Hər bir xanada tam ədəd yazılıb. Cədvəldə yalnız yuxarıdan aşağıya doğru hərəkət etmək mümkündür. Başlanğıcda yuxarı sətirdəki istənilən xananı seçə bilərsiniz və hər dəfə "aşağıdakı qonşu" xanalardan birinə keçə bilərsiniz. Yəni, (i, j) nömrəli xananın (i+1, j-1), (i+1, j) və ya (i+1, j+1) xanasına keçmək olar. Əgər j=M olarsa, üçüncü variant mümkün deyil, j=1 olduqda isə birinci variant mümkün deyil. Marşrut aşağı sətirdəki istənilən xananın üzərində tamamlana bilər.
Elə bir proqram yazın ki, bütün mümkün yollar arasında keçilən xanalardakı dəyərlərin maksimal tək cəmini tapsın. Diqqət yetirin ki, tək olması tələb olunan məhz cəmdir; ayrı-ayrı toplananların tək və ya cüt olması ilə bağlı heç bir məhdudiyyət yoxdur.
Giriş verilənləri
Birinci sətirdə N və M - sətirlərin və sütunların sayı (1 ≤ N, M ≤ 200) verilir. Sonrakı N sətirdə isə hər biri modulu 10^6-dan çox olmayan M boşluqla ayrılmış tam ədəd - cədvəlin xanalarının dəyərləri yazılıb.
Çıxış verilənləri
Tək cəmlər arasında tapılmış maksimal ədədi və ya "impossible" (tırnaq işarələri olmadan, kiçik latın hərfləri ilə) çıxarın. "impossible" yalnız o halda çıxarılmalıdır ki, göstərilən növ marşrutların hamısının cəmi cüt olsun.
Qeyd: Əslində mümkün olan maksimal cəm 42 = 15+9+9+9-dur, lakin 42 cütdür. Buna görə cavab tək cəmlər arasında maksimal olan 39 = 15+9+9+6 olacaq, bu marşrutla əldə edilir: a[1][2], a[2][1], a[3][1], a[4][1].