Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Paša nemrég házat vásárolt Rzanjban. Miután megvette, akkor jött rá, hogy ennek a háznak van egy óriási hiányossága: nincs bekerítve. Most Paša nem tud nyugodtan aludni, mert fél az orosz maffiózóktól és programozóktól, akik bármikor megtámadhatják védtelen házát. Ezért Paša elhatározta, saját maga készít kerítést.
Paša telkét képzeljük el mint egy \(N\times M\) méretű mátrixot, ahol \((i,j)\) azt a mezőt képviseli, amely az \(i\)-edik sorban (felülről), és a \(j\)-edik oszlopban van (balról). Minden mező egy négyzetmétert jelent. Háza teljes egészében az \((A,B)\) mezőben helyezkedik el (Rzanjban a házak nagyon drágák, és Paša házáról nem is állítottuk, hogy nagy). Minden \((i,j)\) mezőhöz tartozik egy \(C_{ij}\) biztonság. Paša téglalap alakú bekerített részt hoz majd létre. A kerítés a mátrix vonalait követi ( Paša tehát az eredeti mátrix egy részmátrixát fogja bekeríteni), ennek belsejében helyezkedik el Paša háza. Oroszországban egy kicsit furcsán definiálják a biztonságos kerítést. Így például a kerítésnek, melynek a bal felső mezője \((x,y)\) a jobb alsó mezője \((z,t)\) és a kerülete \(O\), a biztonsága pontosan \(C_{xy}+C_{zt}+O\).
Paša nem szeretne kockáztatni, ezért a lehető legbiztonságosabb kerítést szeretné elkészíteni, de túlzottan fél az orosz programozóktól, semhogy segítséget kérjen tőlük. Segítsetek neki ti, és mondjátok meg, mekkora a legnagyobb biztonsággal rendelkező kerítés, melyet elkészíthet!
A szabványos bemenet első sorában négy szám áll: a sorok száma (\(N\)), az oszlopok száma (\(M\)) és az \(A,B\) számok, amelyek a ház elhelyezkedését adják meg. A következő \(N\) sor mindegyikében \(M\) természetes szám áll, ahol a \(j\)-edik szám az \((i+1)\)-edik sorban a \(C_{ij}\) érték. Ez pedig az \((i,j)\) mező biztonságának értéke.
A szabványos kimenet első és egyetlen sorában egy számot íratni ki: a legnagyobb biztonságot, amellyel rendelkező kerítést Paša elkészíthet.
3 3 2 2
8 8 1
7 9 5
3 4 7
27
3 3 2 2
1 1 1
1 9 1
1 1 1
22
Az első példa esetében akkor lesz a kerítés biztonsága a legnagyobb, ha a kerítést az egész telek köré helyezi el, amely kerülete \(12\) és akkor a biztonság \(8+7+12=27\).
A második példa esetében az a legjobb megoldás, ha a kerítés közvetlenül a ház körül épül fel, amely a \((2,2)\) mezőn helyezkedik el. Ekkor a kerítés hossza \(4\), és a biztonsága pedig \(9+9+4\) (a \((2,2)\) mező a bal felső és a jobb alsó is egyben).
A tesztpéldák 4 független csoportba oszthatók:
Tesztpéldák, melyek \(20\) pontot érnek: \(N,M \leq 50\).
Tesztpéldák, melyek \(20\) pontot érnek: \(C_{ij} \leq 50\).
Tesztpéldák, melyek \(20\) pontot érnek: \(N,M \leq 400\).
Tesztpéldák, melyek \(50\) pontot érnek: nincs külön korlátozás.
Ivan Pavlov Rzanjban született.