OL11-F. Toshbaqa va tangalar

Toshbaqa n × m o‘lchamli maydonning yuqori chap katagida (1, 1) turibdi, uning uyi esa pastki o‘ng katakda (n, m). Toshbaqa sekin, lekin aqlli: u har qadamda faqat o‘ngga yoki pastga bitta katak yuradi.

Har bir katakda yo aᵢ,ⱼ ta tanga yotibdi, yo katta tosh bor (aᵢ,ⱼ = −1). Toshli katakka kirib bo‘lmaydi. Toshbaqa yo‘lida bosib o‘tgan barcha kataklardagi (boshlang‘ich va oxirgi katak ham) tangalarni yig‘ib oladi. U uyiga eng ko‘pi bilan nechta tanga olib borishi mumkin?

Kirish ma’lumotlari

Birinchi qatorda n va m.
Keyingi n ta qatorning har birida m ta butun son — aᵢ,ⱼ.

Chiqish ma’lumotlari

Bitta son — yig‘ish mumkin bo‘lgan tangalarning eng ko‘p soni. Agar toshbaqa uyiga umuman yetib bora olmasa, -1 chiqaring.

Cheklovlar

1 ≤ n, m ≤ 300; aᵢ,ⱼ = −1 yoki 0 ≤ aᵢ,ⱼ ≤ 10⁴; (1, 1) va (n, m) kataklarda tosh yo‘q.

1–70-testlar 1 balldan, 71–80-testlar 3 balldan, jami 100 ball. 1–2-testlar — shartdagi misollar.

1-misol: 1 → 2 → 4 → 1 → 2 → 3 yo‘li 13 ta tanga beradi (rasmga qarang); bundan yaxshisi yo‘q. Masalan, 1 → 3 yo‘lini tanlasak, keyin o‘ngda ham, pastda ham tosh — toshbaqa qamalib qoladi.

2-misol: (1, 2) va (2, 1) kataklarda tosh bor — toshbaqa joyidan jila olmaydi, javob -1.