7854번 - Water pipe 다국어

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 (x₁, y₁), and the second half — at (x₂, y₂). 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 eastwest direction, and be connected to form a straight line or 90 degree turn. You program must, given L₁, L₂, … L_k — lengths of pipe segments available and C₁, C₂, … C_k — 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 contains integers x₁ y₁ x₂ y₂ k followed by 2k integers L₁ L₂ … L_k C₁ C₂ … C_k

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

• 1 ≤ k ≤ 4,
• 1 ≤ x_i, y_i, L_i ≤ 1000
• 1 ≤ C_i ≤ 10