Задача: Водопровод

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x₁, y₁), а вторая - в точке (x₂, y₂).

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L₁, L₂, ..., L_K и количество отрезков каждой длины C₁, C₂, ..., C_K, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: 1 <= K <= 4, 1 <= x₁, y₁, x₂, y₂, L_i <= 1000, 1 <= C_i <= 10, все числа целые.



Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, K, затем 2_K чисел: L₁, L₂, ..., L_K, C₁, C₂, ..., C_K.

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

Ваш ответ: