시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB183317.647%

문제

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 Vij , allowing you to safely travel to any province at most Rij rows away from row i, and at most Cij columns away from column j (that is, having row number i' and column number j' with |i − i'| ≤ Rij and |j − j'| ≤ Cij). 

In your journey you want to visit N provinces p1, p2, . . . , pN , 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 pk to province pk+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 Vij 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 Rij and Cij (1 ≤ Vij ≤ 1000, 0 ≤ Rij ≤ R and 0 ≤ Cij ≤ C, for i = 1, 2, . . . , R and j = 1, 2, . . . , C). The next N lines describe the provinces p1, p2, . . . , pN you want to visit, in the same order you want to visit them. The k-th of these lines describes the province pk with two integers Ik and Jk, indicating that pk is in row Ik and column Jk (1 ≤ Ik ≤ R and 1 ≤ Jk ≤ 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 pk to province pk+1 using ICPC’s escorted carriage system, or the value −1 if it is impossible to travel from province pk to province pk+1 with this system.

예제 입력 1

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

예제 출력 1

3 -1 1 0

출처

ICPC > Regionals > Latin America > Latin America Regional Contests 2014 J번

  • 문제를 만든 사람: Fidel Schaposnik