有一个包含 $n$ 个顶点的凸多边形。顶点按逆时针方向从 $1$ 到 $n$ 编号，顶点 $i$ 的权值为 $f(i)$。

如果一个顶点子集的权值序列按逆时针顺序构成一个回文序列，我们称该子集是回文的。更正式地说，假设该子集包含 $k$ 个顶点 $v_0, v_1, \dots, 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), \dots, 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$ 的结果。可以证明该值一定是一个整数。

样例

输入 1

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

输出 1

84
0
1

说明

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