#include<cstdio>
#include<algorithm>
#define M 1005
#define i64 __int128
using namespace std;
struct Point{
    long long x,y;
}A[M];
i64 cross(Point a,Point b){
    return i64(a.x)*b.y-i64(a.y)*b.x;
}
int val[M];
i64 sum[M];
int n;
// i64 Get_val(int L,int R){
//     if(L==R)return 0;
//     // printf("<%d %d>\n",L,R);
//     // puts("B");
//     i64 res=0;
//     if(L<=R){
//         if(L)res=sum[R-1]-sum[L-1]+cross(A[R],A[L]);
//         else res=sum[R-1]+cross(A[R],A[L]);
//     }else{
//         if(R==0)res=sum[n-1]-sum[L-1]+cross(A[R],A[L]);
//         else res=sum[n-1]-sum[L-1]+cross(A[R],A[L])+sum[R-1];
//     }
//     // printf("[%d %d]%lld\n",L,R,res);
//     // puts("E");
//     return res;
// }
int lst[M],Nxt[M][M],Pre[M][M];
i64 dp[M][M];
bool In(int Lx,int Rx,int d){
    if(Lx<=Rx)return Lx<=d&&d<=Rx;
    return d>=Lx||d<=Rx;
}
bool mark[M][M];
int B[M],sz;
i64 dfs(int L,int R){
    // printf("[%d %d]\n",L,R);
    if(L==R)return 0;
    if(mark[L][R])return dp[L][R];
    mark[L][R]=true;
    i64 res=cross(A[R],A[L]);
    int p=(L-1+n)%n;
    while(p!=R){
    	int Lx=p,Rx=Pre[p][val[p]];
    	if(!In(L,R,Lx)&&!In(L,R,Rx)){
	    	res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
	    }
    	p=(p-1+n)%n;
	}
    for(int i=0;i<sz;i++){
        int Lx=Pre[L][i],Rx=Nxt[R][i];
        // if(check(Lx,L,R,Rx))continue;
        if(!In(L,R,Lx)&&!In(L,R,Rx)){
	        // printf("[%d %d]-->[%d %d]\n",L,R,Lx,Rx);
	        res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
	    }
//	    Lx=Pre[L][i];Rx=Pre[Lx][i];
//        if(!In(L,R,Lx)&&!In(L,R,Rx)){
//	        res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
//        }
//        
//	    Rx=Nxt[R][i];Lx=Nxt[Rx][i];
//        if(!In(L,R,Lx)&&!In(L,R,Rx)){
//	        res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
//        }
	    
    }
    // printf("dp[%d][%d]=%lld\n",L,R,dp[L][R]);
    return dp[L][R]=res;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&val[i]);
            B[i]=val[i];
        }
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&A[i].x,&A[i].y);
        }
        for(int i=1;i<=n;i++)lst[i]=0;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)mark[i][j]=false;
        // printf("res=%lld\n",res);
        sort(B,B+n);
        sz=unique(B,B+n)-B;
        for(int i=0;i<n;i++)val[i]=lower_bound(B,B+sz,val[i])-B;
        for(int i=0;i<2*n;i++){
            for(int j=0;j<sz;j++){
                Pre[i%n][j]=lst[j];
            }
            lst[val[i%n]]=i%n;
        }
        for(int i=2*n-1;i>=0;i--){
            for(int j=0;j<sz;j++){
                Nxt[i%n][j]=lst[j];
            }
            lst[val[i%n]]=i%n;
        }
        // for(int i=0;i<n;i++){
        //     i64 val=cross(A[i],A[(i+1)%n]);
        //     if(i)sum[i]=sum[i-1]+val;
        //     else sum[i]=val;
        // }
        // puts("Initok");
        i64 res=0;
        for(int i=0;i<n;i++){
            // printf("i=%d\n",i);
            int Lx=i,Rx=Nxt[i][val[i]];
            if(Lx==Rx)continue;
            // printf("@i=%d\n",i);
            // if(Lx==Rx)continue;
            res=max(res,dfs(Lx,Rx)+cross(A[Lx],A[Rx]));
            // printf("@@i=%d\n",i);
        }
        long long ans=res;
        printf("%lld\n",ans);

        // printf("%lf\n",res/2.0);
    }
    return 0;
}