The city AllSquared has been designed by many famous architects and engineers. The city lays in a retangular area of n × m squared miles where n is the height of the rectangle, and m is its width. The streets are horizontal divisions distributed uniformly at every one mile, and the avenues are vertical divisions also uniformly distributed at every one mile. Streets are numbered from north to south, starting from zero; avenues from west to east, also starting from zero. The figure (a) below portrays the city layout for n = 8 and m = 11. The city is also (a) street 0 street 0 (b) 11 22 33 44 55 66 77 88 avenue0 1234567891011 avenue0 1234567891011 divided in horizontal and vertical strips, with the intersection of these strips defining the city subregions (counties). Figure (b) pictures a city divided into 12 counties. Every county is associated with a vehicle circulation fee, which should be paid every time a car enters the county. If the car origin is a street or avenue delimiting the county, there is no fee. For example, in the above figure a car whose origin is street = 2 and avenue = 3 and whose target is street = 2 and avenue = 9 will have to pay only the county crossing fee relative to avenue 6. You should write a program that has the following input: • two strictly positive integers n and m specifying the city dimensions; • two positive integers h and v specifying the number of horizontal and vertical strips, respectively (for the city in the figure, h = 4,v = 3); • h − 1 integers s1,...,sh−1 (1 ≤ si ≤ n − 1) which denote the streets in which there is a county division line (in the previous figure, the numbers are 1, 6, and 7); • v−1integersa1,...,av−1 (1≤ai ≤m−1)whichdenotetheavenuesinwhichthereisacounty division line (in the the previous figure, the numbers are 3 and 6); • the circulation fees for each county in the city, i.e., h ∗ v positive integers p11,p12,...,p1v p21,p22,...,p2v ... ph1,ph2,...,phv where pij is the circulation fee for the county delimited by ai−1 (west), ai+1 (east), sj−1 (north), and sj+1 (south);
2/3 • two pairs of positive integers local1 = (str1, av1) and local2 = (str2, av2) The output should be the smallest possible price to pay for going from local1 to local2. Input The input format may contain several instances of the problem. Each instance is terminated by a line starting with ‘%’ (percentage symbol). The description for one instance has the following format: nm hv s1 s2 ... sh−1 a1 a2 ... av−1 p11 p12 ... p1v p21 p22 ... p2v ... ph1 ph2 ... phv w1 t1 w2 t2 % where • n,m,h,vareintegerssuchthat0<h≤n<100,0<v≤m<100; • s1,...,sh−1 aresuchthat1≤si ≤n−1for1≤i≤h−1; • a1,...,av−1 aresuchthat1≤ai ≤m−1for1≤i≤v−1; • pij are positive integers such that 0 < pij < 10000; • w1,t1,w2,t2 are integers such that 0 ≤ w1,w2 ≤ n and 0 ≤ t1,t2 ≤ m. (w1,t1) is the origin and (w2,t2) is the target point for the problem; • there can be an arbitrary number of spaces or empty lines between the numbers in the file. Output For an input file with k instances of the problem, the output file should follow the format: c1 c2 ... ck where ci is the result for the i-th instance in the input file. Sample Input 100 100 34 30 60 10 70 80 5 100 1 20 1 100 1 20 1 1 1 20 5 5 10 75
3/3 % 8 11 43 167 36 10 10 10 10 10 10 10 10 10 10 10 10 2329 % Sample Output 6 10