Sadə maksimal cəmi
Düzbucaqlı bir cədvəl m sətir və n sütundan ibarətdir. Hər hüceyrədə bir ədəd yerləşdirilib. Siz cədvəlin yuxarı sətirindən başlayaraq aşağıya doğru hərəkət etməlisiniz. Hərəkət edərkən, hər dəfə "aşağıdakı qonşu" hüceyrələrdən birinə keçə bilərsiniz. Yəni, (i, j) nömrəli hüceyrədən ya (i + 1, j - 1), ya (i + 1, j), ya da (i + 1, j + 1) nömrəli hüceyrəyə keçmək mümkündür. Əgər j = n olarsa, yalnız birinci və ikinci variantlar mümkündür, j = 1 olarsa isə yalnız ikinci və üçüncü variantlar mümkündür. Marşrutunuzu aşağı sətirin istənilən hüceyrəsində bitirməlisiniz.
Məqsədiniz, keçilən hüceyrələrin dəyərlərinin maksimum cəmini və bu cəmi əldə etməyin mümkün yollarının sayını tapmaqdır. Yolların sayı 10^9-u keçməyəcək.
Giriş məlumatları
Birinci sətirdə m və n - sətirlərin və sütunların sayı verilmişdir (2 ≤ m ≤ 200, 2 ≤ n ≤ 40, m ≥ n). Sonrakı m sətirdə isə hər biri 10^6 modulunu keçməyən dəqiq n tam ədəd - cədvəl hüceyrələrinin dəyərləri göstərilib.
Çıxış məlumatları
İki ədəd çıxarın - maksimum cəm və yolların sayı.