시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Недавно Вова купил настольную игру <<Морской бой>>. Это пошаговая игра для двух игроков, действие которой разворачивается на просторах бесконечного клетчатого поля. У каждого из игроков есть свой флот, который состоит из нескольких кораблей. Каждый корабль занимает ровно одну клетку поля. Флот каждого из игроков движется по полю с постоянной скоростью --- все корабли $i$-ого игрока каждые $t_i$ шагов перемещается на вектор ($\Delta x_i$, $\Delta y_i$). Таким образом, корабли $i$-ого игрока перемещаются по полю на шагах с номерами 1, $t_i+1$, $2\cdot t_i+1$ и.т.д.

Если на некотором шаге два корабля оказываются в одной клетке --- происходит бой. Бой кораблей является наиболее интересной частью игры, поэтому Вову всегда интересует, через сколько шагов будет первый бой.

Требуется написать программу, которая по заданному расположению кораблей до первого шага игры и их скоростям вычисляет номер шага, на котором будет ближайший бой.

입력

Входной файл содержит описания флотов двух игроков. Описание флота состоит из нескольких строк. Первая строка описания содержит четыре целых числа: $m_i$ ($1 \le m_i \le 10000$) --- число кораблей во флоте $i$-ого игрока, а так же $t_i$ ($1 \le t_i \le 10$), $\Delta x_i$, $\Delta y_i$ ($|\Delta x_i|, |\Delta y_i| \le 10$). 

Затем следуют $m_i$ строк, каждая из которых содержит по два целых числа --- $x_j$ и $y_j$ ($|x_j|, |y_j| \le 10^9$) --- координаты кораблей во флоте до первого шага игры. 

Никакие два корабля, описанные во входном файле, не находятся в начальный момент времени в одной и той же клетке.

출력

В выходной файл необходимо вывести номер шага, на котором произойдет первый бой. Если бой никогда не состоится, выведите в выходной файл -1.

예제 입력 1

3 1 1 0
2 0
1 1
1 -1
2 2 -2 0
8 1
8 2

예제 출력 1

3

예제 입력 2

1 1 2 0
1 1
1 1 -2 0
2 2

예제 출력 2

-1