Normal MaxSum
Müəlliflər günün mövzusunda belə bir məsələnin həllini tapmağınızı istəyirlər: "M ölçülü M sıradan və N sütundan ibarət düzbucaqlı bir cədvəl var. Hər hüceyrədə tam ədəd yerləşdirilib. Bu cədvəldə yuxarıdan aşağıya doğru, yuxarı sıranın istənilən hüceyrəsindən başlayaraq, hər dəfə "aşağıdakı qonşu" hüceyrələrdən birinə keçərək (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ələrə keçmək olar; j = N olduqda yalnız təsvir olunan üç variantdan 1-ci və 2-ci, j = 1 olduqda isə yalnız 2-ci və 3-cü variantlar mümkündür) və marşrutu aşağı sıranın istənilən hüceyrəsində bitirmək lazımdır..."
Əlavə məhdudiyyət qoyulub: yalnız bütün sütunlardan (ən azı bir dəfə) keçən yollar icazəlidir.
Keçilən hüceyrələrin dəyərlərinin mümkün olan maksimum cəmini tapan bir proqram yazın.
Giriş verilənləri
Birinci sətirdə M və N - sətirlərin və sütunların sayı (2 ≤ M ≤ 1024, 2 ≤ N ≤ 768, M ≥ N) verilir, daha sonra növbəti M sətirdə boşluqlarla ayrılmış N tam ədəd, modul üzrə 10^6-dan çox olmayan - cədvəlin hüceyrələrinin dəyərləri yazılıb.
Çıxış verilənləri
Çıxışda tək bir ədəd - maksimum cəm olmalıdır.