Državno natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 3. zadatak - 2. dan

U jednom velikom američkom gradu održava se parada za Dan Zahvalnosti. U paradi sudjeluje velik broj ljudi među kojima se skriva opasni kriminalac kojeg policija pokušava uhvatiti. Kako bi ga napokon uspješno priveli, policajci žele što bolje isplanirati akciju uhidenja.

Parada se održava na području pravokutnog oblika, koje je zapovjedništvo policije podijelilo na jedinične sektore. Da bi lakše isplanirali akciju, na karti su numerirali sektore po recima i stupcima, na način da se gornji lijevi sektor nalazi u prvom retku i prvom stupcu.

Policajci su pokrenuli svoje informatičke sustave i napravili satelitsku snimku parade, a računalo je odmah prebrojalo i ispisalo koliko se ljudi nalazi u svakom pojedinom sektoru. Svi sudionici parade, uključujudi i kriminalca, kredu se toliko polagano da možemo smatrati da se uopde ne kreću.

Kako bi se što lakše približili kriminalcu, policajci su se odlučili pomicati po sektorima u samo dva smjera - dolje ili desno (jer iz suprotnog smjera sije sunce).

Policajci se kredu nepoznatom brzinom, a kada stignu u sektor u kojem se nalazi kriminalac, pričekat de početak akcije.

Kako bi se dodatno osigurali da nede pobuditi sumnju, odlučili su biti malo oprezniji i neprimjetniji. Odlučili su da u svaki sektor sa K sudionika parade smije iz pojedinog smjera udi najviše K/3 policajaca (koristimo cjelobrojno dijeljenje).

Od zapovjedništva policije tog velikog američkog grada dobit dete podatke o broju ljudi u svakom sektoru, položaj svih policajaca na terenu i položaj kriminalca. Zapovjedništvo vas moli da izračunate koliko najviše policajaca može dodi u sektor u kojem se nalazi kriminalac, a da ne izazovu sumnju.

ULAZNI PODACI

U prvom retku nalaze se dva broja R i S ( 1 ≤ R, S ≤ 30 ), visina i širina cijelog područja na kojem se održava parada.

U drugom retku nalaze se dva broja prirodna broja X i Y ( 1 ≤ X ≤ R, 1 ≤ X ≤ S ), koji predstavljaju broj retka i broj stupca sektora u kojem se nalazi kriminalac.

U svakom od slijededih R redaka nalazi se po S cijelih brojeva ai,j ( 0 ≤ ai,j ≤ 6000), koji predstavljaju broj ljudi u sektoru u i-tom retku i j-tom stupcu, ( 1 ≤ i ≤ R, 1 ≤ j ≤ S ).

U sljededem retku se nalazi broj N ( 1 ≤ N ≤ 2000 ), koji predstavlja broj policajaca na terenu. U slijededih N redaka nalaze se po dva prirodna broja xi i yi ( 1 ≤ xi ≤ R, 1 ≤ yi ≤ S ), koji predstavljaju broj retka i stupca sektora u kojem se nalazi i-ti policajac.

IZLAZNI PODACI

U prvi i jedini redak ispisati najvedi mogudi broj policajaca koji mogu stidi u sektor u kojem se nalazi kriminalac bez da izazovu sumnju.

PRIMJERI TEST PODATAKA

ulaz

3 3
3 3
3 3 3
3 3 3
3 3 7
3
1 1
1 3
2 1

izlaz

3

ulaz

3 4
3 2
3 3 3 3
3 3 3 3
3 3 3 3
4
1 2
1 4
2 1
2 3

izlaz

2

ulaz

4 3
4 3
3 6 10
6 7 2
3 6 4
3 3 3
5
1 2
1 3
2 1
2 2
3 1

izlaz

2