Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод ![Копировать номер copy](/images/simple/b_copy.png)
Послать решение Blockly Посылки Темы Где Обсудить (0)
![](1471.gif)
Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке `(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`, если соединение невозможно.
Пример ввода 1
5 5 5 6 1 2 10
Пример ввода 2
20 10 60 50 2 70 30 2 2
Источник: Far-Eastern quarterfinal NEERC, 2003