Codah ClubВежбај. Пошаљи. Напредуј.
Пријави се
Српски
#00061B

P-Detektiv

Pre nego što je postao čuveni detektiv i rešavao svakojake misterije u događajima zabeleženim u igrici L.A. Noire, Cole Phelps je bio samo još jedan obični patrolni policajac, željan slave i uspeha na pokvarenim ulicama Los Anđelesa. Los Anđeles ćemo smatrati kao grad ispresecan ulicama, tako da sva rastojanja u okviru grada posmatramo kao menhetn rastojanja. Menhetn rastojanje između tačaka (a, b) i ([], d) se definiše kao |a - c| + |b - d|.


Cole želi da što pre privuče pažnju svojih nadležnih i dobije unapređenje u detektiva. On zna da će brže uspeti u svom cilju ako rešava "popularnije" slučajeve. Na mapi neke oblasti on u nekom momentu vidi N slučajeva. Cole se uvek nalazi u centralnom polju mape. Osim njega, na ulicama se u svakom momentu nalazi P policajaca i D detektiva. Detektivi su poznati po svojoj lenjosti, zato njih ne zanima koja je popularnost slučajeva kada patroliraju, nego će odgovoriti na onaj poziv koji im je najbliži a ne već zauzet od strane nekog drugog detektiva. Detektivi ne vole da rade u timovima. Više detektiva može otići na isti slučaj samo ako su jednako udaljeni od njega. Pošto su detektivi viši čin od Cole-a, kada oni preuzmu neki slučaj, to znači da Cole ne sme da se meša i taj slučaj je za njega nedostupan. Drugi policajci nisu ambiciozni kao i Cole, oni će juriti slučaj koji im je najbliži, a i zbog nedostatka ambicije će biti spori, toliko da ukoliko je menhetn rastojanje Cole-a do nekog slučaja d1, a menhetn rastojanje nekog policajca od tog slučaja d2, Cole stiže prvi ukoliko važi d1<=2*d2. Policajci nemaju problema sa tim da rade međusobno, tako da će svaki policajac krenuti ka sebi najbližem slučaju koji neki detektiv nije zauzeo iako nema šanse da stigne prvi do njega.


Ukoliko neki detektiv ili policajac ima više slučajeva koji su mu najbliži, on će prigrabiti onaj koji je najzanimljiviji.


Vaš zadatak je da odredite slučaj sa najvećom zanimljivošću koju Cole može prigrabiti prvi.


InputPrva linija standardnog ulaza će sadržati dva cela broja, R i C, (R, C <= 1000) koji predstavljaju dimenzije mape. Druga linija će sadržati tri cela broja N, D i P (0 <= N, D, P <= 1000, D + P < N), koji predstavljaju broj slučajeva, detektiva i policajaca, respektivno. Zatim se u sledećih D redova učitavaju po dva cela broja xdi i ydi koji predstavljaju poziciju i-tog detektiva, pa u sledećih P redova celi brojevi xpi i ypi, koordinate i-tog policajca. U sledećih R redova nalazi se C celih brojeva koji mogu biti 0 (prazno polje) ili K (1 <= K <= 4000), što znači da se na tom polju nalazi slučaj zanimljivosti K.
Zanimljivost svakog slučaja je jedinstvena. Moguće je da se više policajaca i/ili detektiva u početku nalazi na istoj poziciji.
Cole se uvek nalazi u samom centru mape. R i C će uvek biti neparni.

OutputNa standardni izlaz ispisati dva reda. U prvom redu ispisati koordinate slučaja koji će Cole preuzeti, a u drugom zanimljivost tog slučaja.

Ulaz:
[c]5 5
3 1 1
1 1
4 5
0 9 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 8
Izlaz:
2 3
1
Objašnjenje: Cole bi najviše voleo da zgrabi slučaj sa zanimljivošću 9, ali ne može zato što je detektivu na polju (1, 1) taj slučaj najbliži, te će ga on preuzeti. Ne može zgrabiti ni slučaj sa zanimljivošću 8, zato što je policajac na poziciji (4, 5) dovoljno blizu da stigne pre Cole-a. Ostaje mu samo slučaj sa zanimljivošću 1.

Ulaz:
5 5
5 1 2
3 2
1 1
4 4
0 0 0 0 0
0 0 8 0 0
0 0 100 6 0
0 0 9 0 0
0 0 0 0 7
Izlaz:
4 3
9
Objašnjenje: Iako se Cole nalazi na istom polju kao slučaj sa zanimljivošću 100, on nažalost ne može da ga zgrabi zato što je on najbliži detektivu na poziciji (3, 2) Ostaje mu neki od susednih slučajeva, od kojih je najveći onaj sa zanimljivošću 9.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.