printПеребор

printВодопровод

Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке `(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

Пример вывода 1

-1

Пример ввода 2

20 10 60 50 2 70 30 2 2

Пример вывода 2

4
Источник: Far-Eastern quarterfinal NEERC, 2003
loading