MaxSum (Xoşbəxt cəm - 2)
Düzbucaqlı bir cədvəl verilib, ölçüsü N sətir və M sütundur. Hər bir hüceyrədə 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 hüceyrədən başlayaraq, hər dəfə "aşağı qonşu" hüceyrələrdən birinə keçə bilərsiniz. Yəni, (i, j) nömrəli hüceyrədən (i+1, j-1), (i+1, j) və ya (i+1, j+1) nömrəli hüceyrəyə keçmək olar. j=M halında sonuncu üç variantdan biri mümkün olmur, j=1 halında isə birinci. Marşrutu aşağı sətirdəki hər hansı bir hüceyrədə bitirmək mümkündür.
Elə bir proqram yazın ki, bütün mümkün yollar arasında keçilən hüceyrələrin qiymətlərinin maksimal 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 4 və 7 olan natural ədədlərdir. Məsələn, 47, 744, 4 ədədləri xoşbəxtdir, amma 0, 5, 17, 467 ədədləri deyil. Diqqət yetirin ki, xoşbəxt olmalı olan məhz cəmdir, ayrı-ayrı toplananlar deyil.
Giriş verilənləri
Birinci sətirdə N və M - sətirlərin və sütunların sayı (1 ≤ N, M ≤ 12) verilir. Sonrakı N sətirdə isə M boşluqla ayrılmış tam qeyri-mənfi ədədlər (hər biri onluq yazıda ən çox 12 rəqəmli) - cədvəl hüceyrələrinin qiymətləri yazılıb.
Çıxış verilənləri
Ya tək bir tam ədəd (göstərilən növ marşrutların cəmləri arasında tapılan maksimum), ya da "impossible" (tırnaqsız, kiçik latın hərfləri ilə) sətirini çıxarın. "impossible" sətiri yalnız göstərilən növ marşrutlar arasında xoşbəxt cəmi olan heç bir marşrut olmadıqda çıxarılmalıdır.