Водопровід#879
Місто Східне постійно страждає від нестачі води. Для вирішення цієї проблеми було прокладено нову водопровідну трубу. Будівництво труби почалося з обох кінців одночасно, і згодом половини майже з'єдналися. Перша половина труби завершується у точці (x_1, y_1), а друга — у точці (x_2, y_2).
На жаль, залишилося лише декілька відрізків труби різної довжини. Більше того, через особливості місцевої технології труби можуть прокладатися лише у напрямку з півночі на південь або зі сходу на захід і з'єднуються або у пряму, або під кутом градусів.
Знаючи довжини відрізків труб L_1, L_2, \dots, L_K та кількість відрізків кожної довжини C_1, C_2, \dots, C_K, потрібно сконструювати трубу, що з'єднує дві задані точки, або визначити, що це неможливо.
У першому рядку знаходяться числа x_1, y_1, x_2, y_2, , далі чисел: L_1, L_2, \dots, L_K, C_1, C_2, \dots, C_K.
1 \leq K \leq 4, 1 \leq x_1, y_1, x_2, y_2, L_i \leq 1000, 1 \leq C_i \leq 10. Всі числа цілі.
Виведіть одне число: мінімальну кількість необхідних відрізків труб або , якщо з'єднання неможливе.
Приклад 1