시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB65216211827.002%

문제

숙명여자대학교에 입학한 새내기들은 귀여운 눈송이를 좋아해 눈송이 탕후루를 만들려고 한다.

눈송이 모양 과일들이 2차원 좌표상에 있고 꼬치를 $(0, 0)$에서 꼬치의 끝점을 놓을 수 있는 위치 중 하나인 $(e_x, e_y)$까지 놓아 끝점을 포함한 선분상에 있는 모든 과일들을 꽂으려고 한다. 이때 꼬치의 끝점 후보 $M$개가 주어지면 눈송이 과일을 최대한 많이 꽂을 수 있는 위치에서 꽂을 수 있는 과일의 수를 구해보자.

입력

존재하는 과일의 수 $N$과 꼬치의 끝점을 놓을 수 있는 위치의 수 $M$이 정수로 주어진다. ($1 \leq N \leq 300\,000$; $1 \leq M \leq 300\,000$)

다음 $N$개의 줄에 과일의 위치 $(f_x, f_y)$가 공백으로 구분되어 주어진다. ($-10^9 \leq f_x, f_y \leq 10^9$, $f_x$, $f_y$는 정수) 중복된 과일의 위치는 주어지지 않는다.

다음 $M$개의 줄에 꼬치의 끝점을 놓을 수 있는 위치 $(e_x, e_y)$가 공백으로 구분되어 주어진다. ($-10^9 \leq e_x, e_y \leq 10^9$, $e_x$, $e_y$는 정수) 중복된 꼬치의 끝점은 주어지지 않는다.

$(f_x, f_y)$ 또는 $(e_x, e_y)$ 가 $(0, 0)$ 인 경우는 존재하지 않으며 $(f_x, f_y)$와 $(e_x, e_y)$가 같은 경우는 존재할 수 있다.

출력

과일을 최대한 많이 꽂을 수 있을 때 꽂히는 과일의 수를 출력한다.

예제 입력 1

9 5
-1 -1
-1 0
-1 1
1 0
1 1
1 2
2 2
2 4
3 3
0 3
1 1
4 0
4 4
3 6

예제 출력 1

3
  • $(0, 0)$과 $(0, 3)$을 끝점으로 하는 꼬치: 과일 0개

  • $(0, 0)$과 $(1, 1)$을 끝점으로 하는 꼬치: 과일 1개

  • $(0, 0)$과 $(4, 0)$을 끝점으로 하는 꼬치: 과일 1개

  • $(0, 0)$과 $(4, 4)$을 끝점으로 하는 꼬치: 과일 3개

  • $(0, 0)$과 $(3, 6)$을 끝점으로 하는 꼬치: 과일 2개