题目描述

给定一个有 $n$ 个顶点的凸多边形。顶点按逆时针顺序编号从 $1$ 到 $n$（含两端），第 $i$ 个顶点有一个权值 $f(i)$。

称一个顶点的子集是回文的，若它们的权值能够按逆时针顺序组成一个回文序列。更正式地，设子集里有 $k$ 个顶点，它们的编号按逆时针顺序为 $v_0, v_1, \cdots, v_{k - 1}$。需要存在一个整数 $d$ 满足 $0 \le d < k$，且对于所有 $0 \le i < k$ 有 $f(v_{(d + i) \bmod k}) = f(v_{(d - 1 - i) \bmod k})$。

在所有回文的顶点子集中，找出凸包面积最大的子集。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$3 \le n \le 500$）表示凸多边形的顶点数。

第二行输入 $n$ 个整数 $f(1), f(2), \cdots, f(n)$（$1 \le f(i) \le 10^9$），其中 $f(i)$ 表示第 $i$ 个顶点的权值。

对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$）表示第 $i$ 个顶点的坐标。顶点按逆时针顺序列出。保证凸多边形的面积为正，且没有重合的顶点。但可能存在三点共线的情况。

保证所有数据 $n$ 之和不超过 $10^3$。

输出格式

每组数据输出一行一个整数，表示回文顶点子集的最大凸包面积乘以 $2$。可以证明这个值总是一个整数。

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

84
0
1

提示

第一组样例数据如下图所示。选择顶点 $2$，$4$，$5$，$6$，$8$，并考虑 $d = 1$，权值序列 $\{4, 3, 4, 3, 4\}$ 是一个回文序列。

:::align{center} :::