eolymp
bolt
Try our new interface for solving problems
Problems

Plumbing

Plumbing

Time limit 1 second
Memory limit 64 MiB

City East are suffering from water scarcity. To resolve this problem, built a new water pipe. Construction of the pipe started from both ends simultaneously, and after a while half connected. Well, almost. The first half of the pipe ends at the point (x_1, y_1), and the second - at the point (x_2, y_2).

Unfortunately, only a few segments of pipe of different lengths. Moreover, because of the specificity of local technology pipes can be laid only in the direction from north to south or from east to west and join to form or direct, or 90 degree angle. Requires knowing the lengths of the tubes L_1, L_2, ..., L_K and the number of segments each of length C_1, C_2, ..., C_K, to construct a pipeline connecting the two given points, or determine that it is impossible.

Input data

In the first row are the numbers x_1, y_1, x_2, y_2, K, then 2K numbers: L_1, L_2, ..., L_K, C_1, C_2, ..., C_K.

1K4, 1x_1, y_1, x_2, y_2, L_i1000, 1C_i10, all numbers are integers.

Output data

Derive a single number - the minimum number of necessary segments of pipe, or -1 if the connection is impossible.

Examples

Input example #1
5 5 5 6 1 2 10
Output example #1
-1