На плоскость накинута сетка с узлами в точках с целочисленными координатами. В точке (xa, ya) стоит Поликарп, который хочет попасть в точку (xb, yb). У Поликарпа есть набор из n векторов (xv_i, yv_i). Чтобы сделать один шаг из точки (x, y), Поликарп выбирает вектор i из своего набора и переходит в точку (x + xv_i, y + yv_i). Поликарп не может останавливаться во время перехода. Переход всегда происходит от одного узла сетки к другому.

К несчастью для Поликарпа, на плоскости находятся m препятствий в виде отрезков. Поликарп не может пересекать или касаться их во время передвижения. Начальная точка, где находится Поликарп, может принадлежать отрезку, в таком случае он не может двигаться.

Поликарп очень устал и не может сделать больше l шагов. Скажите, за какое минимальное число шагов Поликарп может добраться до конечной точки. Если это невозможно сделать не более, чем за l шагов, выведите  - 1. Каждый вектор можно использовать произвольное число раз.