AL09-3. Tanga yig‘uvchi robot

n × m maydonning har katagida tangalar bor. Robot chap-yuqori burchakdan o‘ng-pastki burchakka boradi va faqat o‘ngga yoki pastga yura oladi. U eng ko‘pi bilan nechta tanga yig‘adi?

Katakka faqat tepadan yoki chapdan kelinadi: dp[i][j] = a[i][j] + max(dp[i−1][j], dp[i][j−1]).

Kirish ma’lumotlari

Birinchi qatorda n m, keyingi n qatorda m tadan son.

Chiqish ma’lumotlari

Eng ko‘p tangalar soni.

Cheklovlar

1 ≤ n, m ≤ 1000, 0 ≤ aᵢⱼ ≤ 1000