eolymp
bolt
Try our new interface for solving problems
Məsələlər

MaxSum əsas

MaxSum əsas

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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 nm~(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ə

Giriş verilənləri #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Çıxış verilənləri #1
42
Müəllif Илья Порублёв
Mənbə Летняя школа Севастополь 2013, Волна 1, День 2