시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

3 초 | 256 MB | 6 | 3 | 3 | 60.000% |

The kingdom of Quadradonia is divided into provinces forming a grid-like pattern of R rows and C columns. Legend has it many wonderful things await discovery in some of the provinces, although it’s unclear if you can actually find the elusive solid form of water stories call “ice”, or if it’s just dragons.

You are planning a trip through the kingdom to find out, but the roads are dangerous so you have to be very careful. To go from one province to another you would like to use the convenient escorted carriage system managed by the Interprovincial Communication & Peregrination Company (ICPC). In each province, the ICPC provides a heavily guarded carriage for you to travel to any other province in a rectangle containing it, at the same flat rate (which may however vary from one province to another). More formally, at the province in the i-th row and the j-th column you can rent an escorted carriage for a cost of V_{ij} , allowing you to safely travel to any province at most R_{ij} rows away from row i, and at most C_{ij} columns away from column j (that is, having row number i' and column number j' with |i − i'| ≤ R_{ij} and |j − j'| ≤ C_{ij}).

In your journey you want to visit N provinces p_{1}, p_{2}, . . . , p_{N} , in that order. Wandering around looking for adventures is an expensive business and your budget is limited, so you would like to spend as little as possible in transportation. Therefore, you would like to calculate the minimum cost of each leg of your trip, that is, the minimum cost of the carriages you have to rent to go from province p_{k} to province p_{k+1}, for k = 1, 2, . . . , N − 1.

The first line contains three integers R, C and N, representing respectively the number of rows, the number of columns and the number of provinces you want to visit (1 ≤ R, C ≤ 500 and 2 ≤ N ≤ 5). Rows are numbered from 1 to R and columns are numbered from 1 to C. The next 3 × R lines describe ICPC’s escorted carriage system by means of three groups of R lines each, with each line containing C integers. In the i-th line of the first group, the j-th number represents the cost V_{ij} of renting a carriage in the province in row i and column j, while the corresponding numbers in the second and third group represent respectively R_{ij} and C_{ij} (1 ≤ V_{ij} ≤ 1000, 0 ≤ R_{ij} ≤ R and 0 ≤ C_{ij} ≤ C, for i = 1, 2, . . . , R and j = 1, 2, . . . , C). The next N lines describe the provinces p_{1}, p_{2}, . . . , p_{N} you want to visit, in the same order you want to visit them. The k-th of these lines describes the province p_{k} with two integers I_{k} and J_{k}, indicating that p_{k} is in row I_{k} and column J_{k} (1 ≤ I_{k} ≤ R and 1 ≤ J_{k} ≤ C for k = 1, 2, . . . , N).

Output a line with N − 1 integers representing the minimum cost of each leg of your trip, or the value −1 if it is impossible to travel using ICPC’s escorted carriage system for that leg. More precisely, for k = 1, 2, . . . , N − 1, the k-th number must be the minimum cost of the carriages you have to rent to go from province p_{k} to province p_{k+1} using ICPC’s escorted carriage system, or the value −1 if it is impossible to travel from province p_{k} to province p_{k+1} with this system.

3 4 5 1 2 1 1 1 5 3 4 1 1 6 3 1 2 3 3 3 3 1 2 0 0 0 1 1 4 0 1 2 3 0 1 4 1 3 1 1 1 3 4 1 1 2 2 2 2

3 -1 1 0