Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (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, затем 2
K чисел: L
1, L
2, ..., L
K, C
1, C
2, ..., C
K.
Выходные данные
Вывести одно число - минимальное количество нужных отрезков труб или -1, если соединение невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 100 1 1 99 1
|
1
|
|
2
|
1 10 10 10 1 10 1
|
-1
|