Treasure Hunt

Time limit10sMemory limit256 MB

Summary

Find the most treasures a single straight line can place on the opposite side from all mines.

Level: Medium7 of 10
Topics: Geometry, Brute force
Solved: No attempts yet

Problem

An island holds $N$ buried treasures and $M$ buried mines. Disarming the mines one at a time is far too dangerous, so you build a single straight fence instead, separating the ground that holds the mines from the ground where the treasure hunt runs.

The fence is a straight line with no thickness that extends forever in both directions, and the island counts as convex. The fence splits the island into two sides, and only the treasures on a side with no mine can be collected safely. No treasure and no mine may lie on the fence itself.

Find the largest number of treasures you can put on a mine free side with one fence.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains the number of treasures $N$ and the number of mines $M$ . Two lines follow, each with $N$ integers. The $i$ -th integer on the first line is the $x$ coordinate of the $i$ -th treasure, and the $i$ -th integer on the second line is its $y$ coordinate. Two more lines follow, each with $M$ integers, giving the $x$ and $y$ coordinates of the mines in the same way.

$0 < T \le 10$
$1 < N \le 300$
$1 < M \le 300$
every coordinate is an integer with $0 \le x, y \le 10^6$
no two objects share a position
no treasure and no mine lies on the fence

Output

For each test case, print on one line the largest number of treasures that a single fence can separate from every mine. Print 0 if no treasure can be separated.

Examples4

Example 1

Input

Expected output

1
2

Example 2

Input

1
2 2
0 1000000
0 0
0 1000000
1000000 1000000

Expected output

Example 3
Input
```
1
3 3
0 2 4
0 0 0
1 3 5
0 0 0
```
Expected output
```
1
```

Example 4

Input

4
4 2
0 4 0 4
0 0 4 4
2 100
2 100
4 2
0 1 2 3
0 0 0 0
1 2
1 1
4 2
0 2 4 1
0 0 0 5
6 3
0 1
4 4
300 200 100 200
200 300 200 100
271 129 129 271
271 271 129 129

Expected output