Codah ClubУпражнявай. Изпращай. Напредвай.
Вход
Български
#00061B

P-Detektiv

Prior to becoming a famous detective and solving various mysteries in the events depicted within the game L.A. Noire, Cole Phelps was just another regular patrol officer, hungry for glory, working on the corrupt streets of Los Angeles. We will consider Los Angeles to be completely intersected with streets, so we will look at a distance between any two points as their manhattan distance. Manhattan distance between points (a, b) and ([], d) is defined as |a - c| + |b - d|.


Cole wants to attract attention from his superiors as soon as possible, so he can get promoted to a detective. He knows that he will fulfill his goal sooner if he solves the more "popular" cases. On the map of an area, at one moment he can locate N cases. Cole is always located in the central point of the map. He can also see the positions of P police officers and D detectives. Detectives are known for being lazy, so they are not interested in the popularity of their cases when they're patrolling. Instead, they will go for the case closest to them, which hasn't already been claimed by another detective. Detectives hate working together, so two detectives can only both work on a single case if their distance from it is the same. Since detectives have a higher rank than Cole, once they claim a case, it means that Cole can not interfere, hence, that case is unavailable for him. Other police officers are not as ambitious as Cole, so they will also go after their closest available case, and they will also be slow. Their speed is so low that if the manhattan distance of Cole to some case is d1 and the manhattan distance from some other officer to that case is d2, Cole will arrive first if d1<=2*d2. Police officers don't have a problem with working together, so every police officer will go after the closest case to him that is available, even if he has no chance of getting to it first.


If a detective or a police officer has multiple available cases closest to him, he will pick the one with the biggest popularity.


Your task is to find the most popular case that Cole can claim first.


InputThe first line of the standard input will contain two integers, R and C, (R, C <= 1000) which represent the map's size. The second line will contain three integers N, D and P (0 <= N, D, P <= 1000, D + P < N), which represent the amount of cases, detectives and officers, respectively. In each of the next D lines there are two integers xdi and ydi, representing the position of the i-th detective, and in the P lines after that the integers xpi and ypi, representing the position of the i-th officer. The next R lines contain C integers which can either be 0 (empty field) or K (1 <= K <= 4000), meaning that a case with popularity K is located there.
Popularity of each case is unique. It is possible for two or more police officers and/or detectives to start off from the same position.
Cole is always located in the centre of the map. R and C will always be odd numbers.

OutputWrite two lines to the standard output. In the first line you should print the coordinates of the case that Cole will claim, and in the second line you should print the popularity of that case.

Input:
[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
Output:
2 3
1
Explanation: Cole would really like to claim the case with popularity 9, but he can't because the detective at (1, 1) will claim it as the case closest to him.. He can't take the case with popularity 8 either, because the officer at position (4, 5) is close enough to reach it before Cole does. This leaves him only with the case of popularity 1.

Input:
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
Output:
4 3
9
Explanation: Even though Cole is located on the same field as a case with an incredible popularity of 100, he unfortunaly can't claim it because it is closest to the detective at (3, 2). This leaves him with one of the adjacent cases to him, out of which the largest one has the popularity 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.