| 主唱迎接您进入生存游戏的最后一轮。 |
有一个正多边形,边长为 $$$n$$$ ($$$n \ge 3$$$)。顶点按顺时针顺序索引为 $$$1,2,\ldots,n$$$。在每个顶点$$$i$$$上,粉红色的士兵都写下了一个正整数$$$a_i$$$。有了这个正多边形,您将玩一个定义如下的游戏。
最初,您的分数为 $$$0$$$。然后,您可以多次执行以下操作来增加您的分数。
- 选择 $$$3$$$ 不同的顶点 $$$i$$$、$$$j$$$、$$$k$$$ 尚未选择 之前,绘制由三个顶点组成的三角形。
- 然后,您的分数增加 $$$a_i \cdot a_j \cdot a_k$$$。
- 但是,你 无法执行此操作 如果该三角形与之前绘制的任何三角形共享正公共面积。
左侧是两次操作后的状态示例。右边的状态 是不可能的 因为两个三角形共享一个正公共面积。 您的目标是最大化分数。请找出您可以从该游戏中获得的最高分数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ — 顶点数 ($$$3 \le n \le 400$$$)。
每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ - 写在顶点上的整数 ($$$1 \le a_i \le 1000$$$)。
保证所有测试用例的$$$n^3$$$总和不超过$$$400^3$$$。
输出
对于每个测试用例,在单独的行中输出您可以获得的最高分数。
示例
输入复制
631 2 342 1 3 462 1 2 1 1 161 2 1 3 1 599 9 8 2 4 4 3 5 399 9 3 2 4 4 8 5 3
输出复制
6 24 5 30 732 696
注意
在第一个测试用例中,您只能绘制一个三角形。通过绘制三角形 $$$i=1$$$、$$$j=2$$$、$$$k=3$$$ 可以找到最高分 $$$6$$$。
在第二个测试用例中,您只能绘制一个三角形。通过绘制三角形 $$$i=1$$$、$$$j=3$$$、$$$k=4$$$ 可以找到最高分 $$$24$$$。
在第三个测试用例中,您可以绘制两个三角形。有一系列的两个操作导致得分$$$5$$$,这是最大值。
在第四个测试用例中,您可以绘制两个三角形。然而,绘制两个三角形会导致得分 $$$6+5=11$$$、$$$15+2=17$$$ 或 $$$10+3=13$$$。通过绘图找到最高分$$$30$$$ 只有一个 三角形,$$$i=2$$$、$$$j=4$$$、$$$k=6$$$。
在第五个测试用例中,您可以绘制三个三角形。最高分 $$$732$$$ 是通过如下绘制三个三角形得出的。