Time limit:   1 second

   Memory limit: 64 megabytes

Figure 1: *
Chemical experiment

Diffusion is the net movement of molecules or atoms from a region of higher concentration(or high chemical potential) to a region of lower concentration(or low chemical potential) by Brownian motion. Diffusion is driven by a gradient in chemical potential of the diffusing species. One of the most influential theory is Kinetic Theory of Gases.

In the present, there is a poison source in an enclosure space of two-dimension. Abnormally, the pressure of every area may not be uniform so that poison things are able to flow towards the neighbor with a less or equal(unavoidable) pressure. Glory has an air pump that has the ability to change the pressure of some areas. Take the tolerance of the whole space into consideration, he only decides to decrease some areas’ pressure and certainly not to subzero. Operations made in different areas might take different costs. Moreover, there are several directed pump tunnels joining two areas, which allow things moving from the starts to the ends regardless of their actual pressure. Of course, Glory’s team is qualified to destroy those tunnels but with a cost. Now he gives you an arduous task. You are asked to prevent poison things from reaching the area where important materials are stored with the lowest costs. Notice, you are not allowed to decrease the pressure of poison source or the storage area.


The input contains several test cases, where the number of test cases is up to 10.

For each test case, the first line contains three integers n, m and K, indicating the space consisting of n × m areas and the number of pump tunnels respectively, where 1 n,m 50 and 0 K 100.

The next line contains four positive integers xS, yS, xT and yT , representing the poison source (xS,yS) and the storage area (xT ,yT ) respectively, where 1 xS,xT n and 1 yS,yT m.

Each of the following n lines contains m non-negative integer indicating the initial pressure of n × m areas, denoted by w1,1,w1,2,w1,m,,w2,1,w2,2,,wn,m, where 0 wi,j 200 000.

And then each of the following n lines contains m non-negative integer indicating the cost of utilizing the pump to decrease unit pressure of n × m areas, denoted by c1,1,c1,2,c1,m, ,c2,1,c2,2,,cn,m, where 1 ci,j 100.

The i-th line of the last K lines contains four positive integers xs, ys, xt, yt and di, indicating it costs di to destroy the i-th tunnel from (xs,ys) to (xt,yt), where 1 xs,xt n, 1 ys,yt m and 1 di 2 000.


For each test case, output a line containing an integer, indicating the minimal costs to present poison things moving from the source to the storage area. If there is no way to make it, output -1.

Sample Input

2 2 1

1 1 2 2

5 4

3 2

2 1

2 2

1 2 2 2 1

Sample Output