Water pipe

The city of Eastowner is perpetually plagued by water shortages, so a new water pipe is being built. Construction started from both ends at the same time, and the two halves were finally joined — almost. The first half ends at point $(x_1, y_1)$ and the second half ends at point $(x_2, y_2)$. Only a few leftover pipe segments of various lengths are available. Because of the peculiarities of local technology, each segment may be laid only in the north–south or the east–west direction, and two segments may be connected only so that they continue in a straight line or make a $90^\circ$ turn (a $180^\circ$ U-turn is not allowed).

Given the available segment lengths $L_1, \dots, L_k$ and the number of segments $C_i$ of each length $L_i$, construct a pipe that connects $(x_1, y_1)$ and $(x_2, y_2)$, or report that it is impossible. Output the minimum number of segments required.

The input contains the integers $x_1\ y_1\ x_2\ y_2\ k$, followed by $2k$ integers $L_1\ L_2\ \dots\ L_k\ C_1\ C_2\ \dots\ C_k$. The values are separated by whitespace (spaces or newlines).

Output a single integer — the minimum number of segments required, or $-1$ if the connection is impossible.

• $1 \le k \le 4$
• $1 \le x_i, y_i, L_i \le 1000$
• $1 \le C_i \le 10$