Zadanie
Irídium a Yrýdium
Počet bodov: 70
Jožko má rád kamene, a tak nečudo, že si založil biznis o ťažení kameňov.
Na záhrade za domom objavil neuveriteľné ložisko dvoch vzácnych surovín - Irídia a Yrýdia. Záhradu si rozdelil na \(r \times c\) parciel, a o každej zistil, koľko Irídia a Yrýdia v nej vie vyťažiť.
Problém je, že nemá ideálny priestor na stavbu tovární na spracovanie týchto rúd. Jeho pozemok je aký je, budú musieť byť na okraji záhrady; Irídium sa bude spracovávať na západe (vľavo),a Yrýdium na severe (hore).
Druhý problém je, že Irídium aj Yrýdium sú ťažké rudy, nebude ich môcť do továrne len tak odniesť na fúriku. Vie si však postaviť dopravné pásy, ktoré ich budú do továrne… dopravovať. Na každú parcelu vie položiť pás, ktorý vyťaženú rudu pošle na susednú parcelu (alebo do továrne, ak je na kraji), vždy v jednom smere.
Druhý bodka prvý problém je, že Irídium a Yrýdium sú nestabilné prvky, a preto ich za žiadnych okolností nesmieme vystaviť odstredivej sile - pri preprave nesmú meniť smer. Ak už cestuje ruda na západ, tak buď ju na nejakej parcele zahodíme, alebo docestuje až do továrne na Irídium. Žiadne kľučkovanie.
Všetko Irídium dopravené do továrne na Yrýdium vyjde nazmar. Podobne, všetko Yrýdium ktoré skončí v továrni na Irídium ostane nespracované.
Pomôžte Jožkovi, a zistite mu, koľko dokopy Irídia a Yrýdia dokáže spracovať, ak si dopravné pásy rozostaví optimálne.
Úloha
Dostanete popis Jožkovej záhrady - pre každú parcelu počet Irídia a Yrýdia (v minimegakilotonách), ktoré z nej vie Jožko vyťažiť.
Ruda bude vyklopená na posuvný pás na jej parcele (ak tam je), a bude posúvaná až kým sa nevysype na parcelu bez pásu alebo do továrne. Pritom sa nesmie dostať na pás, ktorý sa pohybuje v inom smere, ako cestovala doteraz.
Zistite, koľko najviac minimegakiloton (Irídia + Yrýdia) sa dá spracovať.
Vstup a Výstup
V prvom riadku sú dve čísla \(r\) a \(c\): počet riadkov a stĺpcov parciel v Jožkovej záhrade.
Nasledovných \(r\) riadkov obsahuje \(c\) čísel: počet Irídia na jednotlivých parcelách (v minimegakilotonách). Nasledovných \(r\) riadkov obdobne popisuje výskyt Yrýdia v Jožkovej záhrade.
V prvej sade \(1 \leq r,c \leq 50\). V druhej \(1 \leq r, c \leq 600\). Na každej parcele je najviac \(5000\) minimegakiloton Irídia, a najviac \(5000\) minimegakiloton Yrýdia.
Vypíšte jedno číslo: koľko minimegakiloton rudy vie Jožko spracovať zo svojej záhrady.
Príklad
Input:
4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10Output:
98