Перебор

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке `(x_1,\ y_1)`, а вторая – в точке `(x_2,\ y_2)`.

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб `L_1,\ L_2,\ …,\ L_K` и количество отрезков каждой длины `C_1,\ C_2,\ …,\ C_K`, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: `1\ ≤\ K\ ≤\ 4`, `1\ ≤\ x_1,\ y_1,\ x_2,\ y_2,\ L_i\ ≤\ 1000`, `1\ ≤\ C_i\ ≤\ 10`, все числа целые.

В первой строке находятся числа `x_1,\ y_1,\ x_2,\ y_2,\ K`, затем `2K` чисел: `L_1,\ L_2,\ …,\ L_K,\ C_1,\ C_2,\ …,\ C_K`.

Вывести одно число – минимальное количество нужных отрезков труб или `-1`, если соединение невозможно.

5 5 5 6 1 2 10

-1

20 10 60 50 2 70 30 2 2

4