Algoge Judge

Bezbedna podmatrica

Points: 1

Time limit: 1.0s

Memory limit: 64M

Problem type

Paša je nedavno kupio kuću u Rzanju. Međutim, nakon kupovine je shvatio da ova kuća ima jednu strašnu manu: ona nema ogradu! Sada Paša ne može mirno da spava jer strahuje od ruskih mafijaša i programera koji u svakom trenutku mogu da napadnu na njegovu nezaštićenu kuću. Stoga, Paša je preuzeo pravljenje ograde u sopstvene ruke.

Pašin plac se može zamisliti kao matrica dimenzija $N\times M$ ~N\times M~, gde $(i,j)$ ~(i,j)~ predstavlja polje u preseku $i$ ~i~-te vrste (od vrha) i $j$ ~j~-te kolone (od leva) i svako polje predstavlja jedan kvadratni metar. Njegova kuća se nalazi kompletno u polju $(A,B)$ ~(A,B)~ (niko nikad nije rekao da je Pašina kuća nešto velika, kuće u Rzanju su skupe). Svako polje $(i,j)$ ~(i,j)~ ima neku bezbednost $C_{ij}$ ~C_{ij}~. Paša hoće da izgradi ogradu u obliku pravougaonika tako da ograda prati linije matrice (u prevodu, Paša će ograditi jednu podmatricu početne matrice) i da u svojoj unutrašnjosti sadrži njegovu kuću. U Rusiji imaju malo nestandardnu definiciju bezbednosti pa se smatra da je bezbednost ograde čije je gornje levo polje $(x,y)$ ~(x,y)~, donje desno polje $(z,t)$ ~(z,t)~ i obim $O$ ~O~ metara upravo $C_{xy}+C_{zt}+O$ ~C_{xy}+C_{zt}+O~.

Paša ne želi ništa da rizikuje, stoga želi da izgradi što je moguće bezbedniju ogradu, ali se previše plaši ruskih programera da bi njima zatražio pomoć. Zato je pitao vas da mu kažete kolika je najveća moguća bezbednost ograde koju on može da izgradi.

Opis ulaza

Prva linija standardnog ulaza sadrži četiri broja, broj vrsta $N$ ~N~, broj kolona $M$ ~M~ i vrednosti $A,B$ ~A,B~ koje opisuju lokaciju njegove kuće. Narednih $N$ ~N~ linija sadrže po $M$ ~M~ prirodnih brojeva: gde $j$ ~j~-ti broj u $(i+1)$ ~(i+1)~-voj liniji predstavlja broj $C_{ij}$ ~C_{ij}~, koji označava bezbednost polja $(i,j)$ ~(i,j)~.

Opis izlaza

U prvu i jedinu liniju standardnog izlaza ispisati jedan broj: najveću moguću bezbednost ograde koju Paša može da izgradi.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Objašnjenje primera

Za prvi primer, najveća vrednost bezbednosti ograde je u slučaju da postavi ogradu oko celog placa koji ima obim $12$ ~12~ i stoga je bezbednost $8+7+12=27$ ~8+7+12=27~.

U drugom primeru je optimalno da se izgradi ograda samo oko Pašine kuće koja se nalazi u polju $(2,2)$ ~(2,2)~, tada ograda ima obim $4$ ~4~ i njena bezbednost je $9+9+4$ ~9+9+4~ (polje $(2,2)$ ~(2,2)~ se računa i kao gornje levo i kao donje desno polje).