给定一个有 个顶点的凸多边形。顶点按逆时针顺序编号从 到 （含两端），第 个顶点有一个权值 。
称一个顶点的子集是回文的，若它们的权值能够按逆时针顺序组成一个回文序列。更正式地，设子集里有 个顶点，它们的编号按逆时针顺序为 。需要存在一个整数 满足 ，且对于所有 有 。
在所有回文的顶点子集中，找出凸包面积最大的子集。
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入一个整数 （）表示凸多边形的顶点数。
第二行输入 个整数 （），其中 表示第 个顶点的权值。
对于接下来的 行，第 行输入两个整数 和 （）表示第 个顶点的坐标。顶点按逆时针顺序列出。保证凸多边形的面积为正，且没有重合的顶点。但可能存在三点共线的情况。
保证所有数据 之和不超过 。
每组数据输出一行一个整数，表示回文顶点子集的最大凸包面积乘以 。可以证明这个值总是一个整数。
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
第一组样例数据如下图所示。选择顶点 ，，，，，并考虑 ，权值序列 是一个回文序列。
:::align{center} :::
:::