Masala #0106

Xotira 128 MB Vaqt 1000 ms
14

Matritsa

Sizda N ta qator va M ta ustundan iborat matritsa berilgan. Siz matritsa ustida o’yin o’ynayapsiz. O’yin shartlari quyidagicha:

  • Siz o’yinni matritsaning 1-satrining ixtiyoriy elementidan boshlashingiz mumkin.
  • Siz o’yin mobaynida qadam qo’ygan yacheykangizdagi qiymat sizning umumiy balingizga qo’shiladi va shundan so’ng bu yacheykadagi qiymat 0 ga almashiladi.
  • Siz o’yin mobaynida har bir harakatda chapga, o’ngga va pastga bir yacheyka birligida harakatlana olasiz
  • Siz o’yinni matritsaning oxirgi qatorining ixtiyoriy yacheykasida yakunlashingiz mumkin

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida ikkita butun son, N va M(1 ≤ N*M ≤ 4*106). Keyingi N ta satrning har birida M tadan [-250, 250] oralig’idagi butun son, matritsa elementlari kiritiladi.


Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, siz yig’ishingiz mumkin bo’lgan maksimal qiymatni chop eting


Misollar
# input.txt output.txt
1
4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20
37
Izoh: