|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|4 초||512 MB||25||18||18||75.000%|
On a sunny day, there was an abduction incident at a crossing in a city. It is suspected that the criminals were Anna and Bruno, and they escaped from the abduction scene by a car. The car was not yet found. The police is searching it even now.
The urban area where the criminals was driving the car is a city of rectangular grid with H streets running in the east-west direction and W streets running in the south-north direction. The distance between two adjacent crossings is 1 kilometer.
Each street has an integer, the congestion degree. The congestion degree of the i-th street (1 ≤ i ≤ H) from north running in the east-west direction is Ai , and the congestion degree of the j-th street (1 ≤ j ≤ W) from west running in the south-north direction is Bj. These H + W values are different from each other. For each street, the congestion degree has the same value at any points on it.
The investigation by the police revealed that the criminals moved in the city in the following way:
There are Q candidates of crossings for the abduction scene. These Q candidates are different from each other. To determine the number of investigators, the police wants to know, for each candidate of crossings, the maximum possible travel distance for the criminals assuming the abduction incident was occurred at that place.
For each of Q queries, calculate the maximum possible travel distance from the given candidate of crossings.
Given the congestion degrees of the streets in the city and Q candidates of crossings for the abduction scene, write a program which calculates the maximum possible travel distance from each candidate of crossings.
Read the following data from the standard input.
Write Q lines to the standard output. The k-th line of output should contain an integer, the maximum possible travel distance (in kilometers) from the k-th candidate of crossings for the abduction scene.
H ≤ 8, W ≤ 8, Q = 1.
H ≤ 2 000, W ≤ 2 000, Q = 1.
Q = 1.
H ≤ 2 000, W ≤ 2 000.
There are no additional constraints.
3 3 5 3 2 6 1 4 5 1 1 1 2 2 2 3 1 3 3
4 5 4 4 2
For example, for the third query, the travel distance achieves the maximum value if the criminals moved in the following way:
If they moved as above, the travel distance is 4 kilometers.
4 5 6 30 10 40 20 15 55 25 35 45 1 3 4 3 2 2 4 1 2 5 3 3
7 6 9 4 6 9