Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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'| \leq 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 \leq R, C \leq 500$ and $2 \leq N \leq 5$). Rows are numbered from $1$ to $R$ and columns are numbered from $1$ to $C$. The next $3 \times 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 \leq V_{ij} \leq 1000$, $0 \leq R_{ij} \leq R$ and $0 \leq C_{ij} \leq 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 \leq I_k \leq R$ and $1 \leq J_k \leq 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.