MaxSum (Xoşbəxt cəmi - 1)#5860
Düzbucaqlı bir cədvəl var, ölçüsü sətir və sütun. Hər bir xanada tam ədəd yazılıb. Cədvəldə yuxarıdan aşağıya doğru hərəkət etmək mümkündür. Yuxarı sətirdəki istənilən xananı seçərək, hər dəfə "aşağıdakı qonşu" xanalardan birinə keçə bilərsiniz. Yəni, nömrəli xananın (i+1, j-1), (i+1, j) və ya (i+1, j+1) xanasına keçmək olar. j = M olduqda, sonuncu üç variantdan biri mümkün olmur, j = 1 olduqda isə birinci. Marşrutu aşağı sətirdəki istənilən xananın üzərində tamamlamaq olar.
Elə bir proqram yazın ki, göstərilən marşrutlar arasında keçilən xanalardakı dəyərlərin mümkün olan ən böyük xoşbəxt cəmini tapsın. Hər kəsə məlumdur ki, xoşbəxt ədədlər yalnız xoşbəxt rəqəmlər və olan natural ədədlərdir. Məsələn, , , ədədləri xoşbəxtdir, amma , , , ədədləri xoşbəxt deyil. Diqqət yetirin ki, xoşbəxt olmalı olan məhz cəmdir, ayrılıqda toplananlar deyil.
Birinci sətirdə və (1 \leq N, M \leq 77) – sətirlərin və sütunların sayı verilir. Sonrakı sətirdə isə hər sətirdə məhz boşluqla ayrılmış tam ədədlər (0 \leq a_{ij} \leq 77) – cədvəlin xanalardakı dəyərləri yazılıb.
Ya tək bir tam ədəd (göstərilən marşrutlar üzrə tapılan maksimum cəm), ya da **impossible** (tırnaqsız, kiçik latın hərfləri ilə) sətrini çıxarın. **impossible** yalnız göstərilən marşrutlar arasında xoşbəxt cəmi olan heç bir marşrut olmadıqda çıxarılmalıdır.
Nümunə 1