클라우드 리테이너의 게임

Qingyun Peak 위 구름 속 거처(Dwelling)를 만든 Cloud Retainer는 역학에 깊은 관심이 있다. 리월의 등불 축제까지는 한 달이 넘게 남았지만, 그녀는 이미 이 축제를 위한 게임 이벤트 설계를 시작했다.

Cloud Retainer와 여행자

이 게임의 핵심은 공을 발사해 점수를 최대한 높이는 것이다. 게임은 두 수평선 $y = 0$과 $y = H$ 사이의 2차원 평면에서 진행된다. 두 선 사이에는 $n$개의 작은 나무 판자와 $m$개의 동전이 있으며, 둘 다 한 점으로 본다. $i$번째 나무 판자는 $(x_i, y_i)$에, $i$번째 동전은 $(x'_i, y'_i)$에 있다.

플레이어는 $(10^{-9}, 10^{-9})$에서 공을 발사한다. $\overrightarrow{v} = (v_x, v_y)$를 공의 속도라고 하자. 공이 $(x, y)$에 있으면 $\epsilon$초 뒤에 $(x + v_x\epsilon, y + v_y\epsilon)$로 이동한다. 처음 속도는 $\overrightarrow{v} = (1, 1)$이다.

공이 나무 판자나 두 수평선 중 하나에 부딪히면 $v_y$의 부호가 바뀌고 $v_x$는 그대로다. 공이 동전에 부딪히면 점수가 1 오르고 속도는 변하지 않는다.

플레이어는 발사 전에 나무 판자를 원하는 만큼 제거할 수 있다. 하나도 제거하지 않아도 된다. 클라우드 리테이너는 이 게임의 난이도를 가늠하고 싶어 한다. 최적의 전략을 쓸 때 $10^{10^{10^{10^{10}}}}$초가 지난 뒤 플레이어가 얻을 수 있는 최대 점수를 구하시오.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음 형식이다.

첫 줄에 $H$ ($2 \le H \le 10^9$)가 주어진다.

둘째 줄에 나무 판자의 수 $n$ ($1 \le n \le 10^5$)이 주어진다. 이어서 $n$개의 줄에 $i$번째 나무 판자의 좌표 $x_i$, $y_i$ ($1 \le x_i \le 10^9$, $1 \le y_i < H$)가 한 줄에 하나씩 주어진다.

다음 줄에 동전의 수 $m$ ($1 \le m \le 10^5$)이 주어진다. 이어서 $m$개의 줄에 $i$번째 동전의 좌표 $x'_i$, $y'_i$ ($1 \le x'_i \le 10^9$, $1 \le y'_i < H$)가 한 줄에 하나씩 주어진다.

한 테스트 케이스의 $n + m$개의 점은 모두 서로 다르다. 모든 테스트 케이스에 걸친 $n$의 합과 $m$의 합은 각각 $5 \times 10^5$을 넘지 않는다.

각 테스트 케이스마다 나무 판자를 일부 제거하거나 하나도 제거하지 않았을 때 얻을 수 있는 최대 점수를 한 줄에 출력한다.

아래 그림은 테스트 케이스 두 개를 보여 준다. 채워진 다이아몬드는 남은 나무 판자, 빈 다이아몬드는 제거된 나무 판자, 원형 점은 동전이다.

테스트 케이스 1	테스트 케이스 2