Plumbing#879
City East is constantly suffering from water scarcity. To resolve this problem, a new water pipe was constructed. Construction of the pipe started from both ends simultaneously, and after some time, the halves nearly met. The first half of the pipe ends at point (x_1, y_1), and the second half at point (x_2, y_2).
Unfortunately, only a few pipe segments of different lengths remain. Moreover, due to the specifics of the local technology, pipes can only be laid in the direction from north to south or from east to west, and are joined either in a straight line or at an angle of degrees.
Knowing the lengths of the segments L_1, L_2, \dots, L_K and the number of segments of each length C_1, C_2, \dots, C_K, construct a pipeline connecting the given points, or determine that it is impossible.
The first line contains the numbers x_1, y_1, x_2, y_2, , followed by numbers: L_1, L_2, \dots, L_K, C_1, C_2, \dots, C_K.
1 \leq K \leq 4, 1 \leq x_1, y_1, x_2, y_2, L_i \leq 1000, 1 \leq C_i \leq 10. All numbers are integers.
Output a single number: the minimal number of pipe segments needed, or if the connection is impossible.
Example 1