Problem Description

Translated from ROI 2022 D1T4.

On the Cartesian plane, there is a rectangular region whose four corners are at $(0, 0)$, $(w, 0)$, $(w, h)$, and $(0, h)$. There are $n$ lamps in this region. The $i$-th lamp is located at $(x_i, y_i)$.

Each lamp illuminates a $90$-degree angle. The sides of this angle are parallel to the coordinate axes, and its vertex is at the lamp’s position. Therefore, each lamp has four possible illumination directions:

You are given a set of allowed angle directions (the same for all lamps). For each lamp, choose one direction from the allowed set. You need to illuminate as large an area as possible. A point is considered illuminated if it is illuminated by at least one lamp.

Compute the maximum possible illuminated area using the lamps, where each lamp points in one of the allowed directions.

Input Format

Each test point contains multiple test cases.

The first line contains an integer $k (1 \le k \le 4)$, the number of allowed angle directions in each test case.

The second line contains $k$ integers, the indices of the allowed directions (for example, if the light is allowed to shine to the upper-right or lower-left, the input is 1 3). All $k$ numbers are distinct and are given in increasing order.

The third line contains an integer $t (1 \le t \le 10000)$, the number of test cases. Then follow $t$ test cases.

The first line of each test case contains three integers $n, w, h (1 \le n \le 100000, 1 \le w, h \le 10^9)$, representing the number of lamps in the region and the size of the region.

The next $n$ lines each contain two integers $x_i, y_i (0 \le x_i \le w, 0 \le y_i \le h)$, representing the coordinates of the $i$-th lamp. It is guaranteed that no two lamps are at the same point.

Output Format

For each test case, output one integer, the maximum possible illuminated area.

1
1
1
4 6 4
3 3
1 2
4 1
5 0

13

2
1 2
1
4 9 7
3 0
0 5
4 4
1 2

55

2
1 3
1
5 6 11
4 2
2 7
1 10
3 8
5 4

57

3
1 2 3
1
5 7 10
1 9
5 5
3 4
2 6
4 3

63

4
1 2 3 4
1
3 8 6
2 2
4 5
6 1

44

Hint

Sample Explanation:

Sample $1$:

Sample $2$:

Sample $3$:

Sample $4$:

Sample $5$:

Constraints:

The full constraints are given in the input format.

Translated by ChatGPT 5