Maksimal məbləğ və yolların sayı
Düzbucaqlı bir cədvəl var, ölçüsü n sətir və m 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 xanadan başlayaraq, hər dəfə "aşağıdakı qonşu" xanalardan birinə keçə bilərsiniz. Yəni, (i, j) nömrəli xananın üzərindən (i + 1, j - 1) və ya (i + 1, j) və ya (i + 1, j + 1) nömrəli xanaya keçmək olar. j = m halında, təsvir olunan üç variantdan sonuncusu mümkün olmur, j = 1 halında isə birincisi mümkün deyil. Marşrutu aşağı sətirin istənilən xanada bitirmək olar.
Maksimum mümkün keçilən xanalardakı dəyərlərin cəmini və bu cəmin əldə edildiyi yolların sayını tapacaq bir proqram yazın.
Giriş məlumatları
Birinci sətirdə n və m (1 ≤ n, m ≤ 200) - sətirlərin və sütunların sayı verilir. Sonrakı n sətirdə isə dəqiq m tam ədəd (hər biri modulu 10^6-dan çox olmayan) - cədvəlin xanalardakı dəyərləri yazılıb.
Məlumdur ki, maksimum cəmi olan yolların sayı 10^9-dan çox deyil.
Çıxış məlumatları
İki tam ədəd çıxarın - maksimum cəm və yolların sayı.
İzah
Birinci testdə maksimum dəyər 42 yalnız bir yolla əldə edilə bilər (15 + 9 + 9 + 9). İkinci testdə maksimum dəyər 111 üç yolla əldə edilə bilər: a[1][3] = 100, a[2][2] = 1, a[3][1] = 10, və ya a[1][3] = 100, a[2][3] = 10, a[3][2] = 1, və ya a[1][3] = 100, a[2][3] = 10, a[3][3] = 1.