题目描述

译自 ROI 2022 Day1 T4. Прожекторы

在坐标平面上，有一个四个角位于 $(0, 0), (w, 0), (w, h), (0, h)$ 的矩形区域。在这个区域内有 $n$ 个投影灯，第 $i$ 个投影灯位于坐标 $(x_i, y_i)$。

每个投影灯都能照亮一个 $90^\circ$ 的角，其两边与坐标轴平行，顶点位于投影灯的位置。因此，每个投影灯有四个可能的照亮方向：

给定一组合法的照亮方向，对于所有投影灯都相同。对于每个投影灯，你可以选择一个合法的方向。任务是使用投影灯照亮尽可能大的区域。如果一个点至少被一个投影灯照亮，那么这个点就被认为是照亮的。

计算出通过将每个投影灯设置在一个合法的方向上，可以照亮的区域的最大可能面积。

输入格式

输入包含多组数据。

第一行包含一个整数 $k\ (1 \le k \le 4$)，表示所有输入数据的投影灯角度方向的数量。第二行包含 $k$ 个整数表示合法的方向编号。所有 $k$ 个数字都是不同的，并按升序排列。

第三行包含一个整数 $t\ (1 \le t \le 10^4)$，表示测试数据的组数。

每组输入数据的第一行包含三个整数 $n,w,h\ (1 \le n \le 10^5,1 \le w, h \le 10^9)$，表示场地上的投影灯数量和场地的尺寸。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i\ (0 \le x_i \le w,0 \le y_i \le h)$，表示第 $i$ 个投影灯所在点的坐标。保证没有两个投影灯位于同一点。

输出格式

对于每组输入数据，输出一个整数表示可以用投影灯照亮的区域的最大面积。

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

数据范围与提示

令 $\sum n$ 表示所有输入数据集中投影灯的总数。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。