Problem C. Water pipe

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:200 Mb
Output file:output.txt  


The Eastowner city is perpetually haunted with water supply shortages, so in order to remedy this problem a new water-pipe 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 north-south or east-west 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.

Input file format

Input file contains integers x1 y1 x2 y2 k followed by 2k integers L1 L2 … Lk C1 C2 … Ck

Output file format

Output file must contain a single integer — the number of required segments, or −1 if the connection is impossible.


1 ≤ k ≤ 4, 1 ≤ xi, yi, Li ≤ 1000, 1 ≤ Ci ≤ 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
20 10 60 50 2 70 30 2 2
5 5 5 6 1
2 10

0.075s 0.012s 15