|
Водопровод
(Время: 1 сек. Память: 16 Мб Сложность: 78%)
Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x1, y1), а вторая - в точке (x2, y2).
К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов.
Требуется, зная длины отрезков труб L1, L2, ..., LK и количество отрезков каждой длины C1, C2, ..., CK, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
Входные данные
Входной файл INPUT.TXT содержит целые числа, разделенные пробелом: x1, y1, x2, y2, K, L1, L2, ..., LK, C1, C2, ..., CK (1 ≤ K ≤ 4, 1 ≤ x1, y1, x2, y2, Li ≤ 1000, 1 ≤ Ci ≤ 10).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимальное количество нужных отрезков труб или -1, если соединение невозможно.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 5 5 6 1 2 10 | -1 |
2 | 20 10 60 50 2 70 30 2 2 | 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |