URI Online Judge | 1752
# Journey Through The Kingdom

**Timelimit: 10**

By Fidel I. Schaposnik Massolo, Universidad Nacional de La Plata Argentina

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

In your journey you want to visit *N* provinces *p _{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

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

Input Sample | Output Sample |

3 4 5 |
3 -1 1 0 |