
ZOJ Problem Set  2439
The Eastowner city is perpetually haunted with water supply shortages, so in order to remedy this problem a new waterpipe has been built. Builders started the pipe from both ends simultaneously, and after some hard work both halves were connected. Well, almost. First half of pipe ended at a point (x1, y1), and the second half  at (x2, y2). Unfortunately only few pipe segments of different length were left. Moreover, due to the peculiarities of local technology the pipes can only be put in either northsouth or eastwest direction, and be connected to form a straight line or 90 degree turn. You program must, given L1, L2, ..., Lk  lengths of pipe segments available and C1, C2, ..., Ck  number of segments of each length, construct a water pipe connecting given points, or declare that it is impossible. Program must output the minimum required number of segments. Constraints 1 <= k <= 4, 1 <= xi, yi, Li <= 1000, 1 <= Ci <= 10
Input contains integers x1 y1 x2 y2 k followed by 2k integers L1 L2 ... Lk C1 C2 ... Ck
Output must contain a single integer  the number of required segments, or 1 if the connection is impossible.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between
output blocks.
2
4 Source: Northeastern Europe 2003, FarEastern Subregion 