MaxSum əsas

$n$ sətir və $m$ sütun ehtiva edən düzbucaqlı cədvəl verilir. Hər bir xanada tam ədəd yazılıb. Bu cədvəldə ilk üst sətrin istənilən xanasından başlayaraq yuxarıdan aşağıya doğru hər dəfə qonşu xanaya keçməklə hərəkət etmək olar (başqa sözlə, $(i,j)$ nömrəli xanadan $(i+1,j-1)$, $(i+1,j)$ və ya $(i+1,j+1)$ nömrəli xanaya keçmək olar). $j=m$ halında verilmiş üç variant mümkün deyil, $j=1$ olanda isə birinci variant mümükün olmur). Marşurut sonuncu sətrin hər hansı bir xanasında sona çatır.

Bütün mümkün yollar arasından cəmi maksimum olan yolu tapan proqramı tərtib edin.

Giriş verilənləri

İlk sətirdə sətirlərin və sütunlarin sayını ifadə edən $n$ və $m(1\le n,m\le 200)$ ədədləri verilir, sonra növbəti hər bir $n$ sətirdə cədvəlin xanalarının qiymətini ifadə edən boşluqla ayrılmış $m$ sayda tam ədəd verilir (hər bir ədəd modulca $10^6$-nı aşmır).

Çıxış verilənləri

Tapılan yeganə maksimal cəmi verməli.

Nümunələr