Problem I
Thin Ice

Uolevi er staddir á ferningslaga frosinni tjörn sem skipta má í $n \times m$ ferningslaga reiti. Á hverjum reit liggur ein króna. Einnig hefur hver reitur vissa ísþykkt og getur því aðeins þolað einhvern hámarksfjölda króna áður en ísinn brotnar.

Í hverju skrefi getur Uolevi fært sig einn reit upp, niður, hægri eða vinstri en hann getur ekki farið útfyrir tjörnina. Ef það er króna á reitnum sem hann er á getur Uolevi týnt hana upp. Uolevi má ekki færa sig yfir á reit nema hann geti borið þyngd krónanna. Þetta telur bæði krónurnar sem hann er með á sér og krónuna sem er þegar þar, ef Uolevi er ekki þegar búinn að týna hana upp. Þyngd Uolevi er svo lítil að hún skiptir ekki máli.

Uolevi vill byrja einhversstaðar á jaðar tjarnarinnar og enda aftur á jaðrinum, ekki endilega á sama stað. Hver er hámarksfjöldi króna sem hann getur safnað og farið með út á jaðarinn í einni ferð?

Inntak

Fyrsta lína inntakins inniheldur heiltölurnar $n$ og $m$, hæð og breidd tjarnarinnar. Næst fylgja $n$ línur hver með $m$ heiltölum $d$, fjöldi króna sem hver ísreitur getur borið.

Úttak

Prentið hámarksfjölda króna sem Uolevi getur safnað.

Stigagjöf

Útskýring á sýnidæmum

Í sýniinntaki getur Uolevi byrjað á reitnum efst til vinstri. Hann fer svo niður um einn og týnir upp krónuna. Næst fer hann til hægri og týnir upp þá krónu. Svo fer hann niður, svo til vinstri og týnir upp þá krónu. Svo færir hann sig til hægri og týnir upp krónu í tvígang. Hann er nú á neðri jaðar og getur hætt þar og nær því að safna fimm krónum. Hann getur ekki safnað sex eða fleiri krónum því enginn jaðarreitur getur borið sex eða fleiri krónur.

3 4
1 1 1 1
1 3 6 1
3 4 5 1

5