#include <bits/stdc++.h>
using namespace std;

const int N = 505;
const long long inf = 0x3f3f3f3f3f3f3f3f;

int T, n, m, a[N], b[N];
long long all, ans, val[N], sump[N], sums[N], f[N][N], g[N][N];

struct P {
	long long x, y;

	P (long long x = 0, long long y = 0):
		x(x), y(y) {}

	P operator + (const P &b) {
		return P(x + b.x, y + b.y);
	}

	P operator - (const P &b) {
		return P(x - b.x, y - b.y);
	}
} p[N];

long long outp(const P &a, const P &b) {
	return a.x * b.y - b.x * a.y;
}

long long get(int i, int j) {
	if (i > j) {
		return sums[i] + sump[j] + abs(outp(p[i] - p[0], p[j] - p[0]));
	} else {
		return sump[j] - sump[i] - abs(outp(p[i] - p[0], p[j] - p[0]));
	}
}

void work() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b, b + n);
	m = unique(b, b + n) - b;
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(b, b + m, a[i]) - b;
	}
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	for (int i = 2; i < n; i++) {
		val[i] = abs(outp(p[i] - p[0], p[i - 1] - p[0]));
	}
	for (int i = 2; i < n; i++) {
		sump[i] = sump[i - 1] + val[i];
	}
	all = sump[n - 1];
	sums[n - 1] = 0;
	for (int i = n - 2; i >= 1; i--) {
		sums[i] = sums[i + 1] + val[i + 1];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			f[i][j] = inf;
			g[i][j] = inf;
		}
	}
	ans = 0;
	for (int len = 1; len < n; len++) {
		for (int i = 0; i < n; i++) {
			int j = (i + len) % n;
			if (a[i] == a[j]) {
				f[i][j] = min(f[i][j], get(i, j));
			}
			ans = max(ans, all - f[i][j] - get(j, i));
			for (int k = i - 1; k != j; k = (k + n - 1) % n) {
				g[k][j] = min(g[k][j], f[i][j] + get(k, i));
			}
			for (int k = j + 1; ; k = (k + 1) % n) {
				if (a[i] == a[k]) {
					f[i][k] = min(f[i][k], g[i][j] + get(j, k));
				}
				if (k == i) {
					break;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		ans = max(ans, all - f[i][i]);
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while (T--) {
		work();
	}

	return 0;
}