logo AlgoBeat OnlineJudge
登录 注册

#135. 【模板】模拟退火

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

电车难题指的是如下一个心理学问题:

假设在一个电车上被绑了 5 个人,而它的备用轨道上被绑了 1 个人,又有一辆失控的电车飞速驶来,而你身边正好有一个摇杆,你可以推动摇杆来让电车驶入备用轨道,杀死那 1 个人,救下 5 个人。你也可以什么也不做,杀死 5 个人,救下 1 个人。眼看电车就要驶入那片区域了,你必须在很短的时间内做出决定,杀死 1 个人,救下 5 个人,还是杀死 5 个人,救下 1 个人……

但是很遗憾,今天我们要讨论的问题,与轨道上的 6 个人无关……

电车上有 名喜欢说批话的 Oler。他们上车之后,找到一排座位准备坐下。正当大家都有说有笑之时,一个不和谐的声音打破了欢乐的氛围:

“谁强谁先坐。”

于是 位同学开始互相谦让了。你看到了这 位面对一排空座位还站着同学的同学们,有些疑惑不解,于是你决定给他们安排落座。

名同学的编号为 ,你要求 位同学按照编号从小到大的顺序入座。然而前面的同学可能会在坐下的时候说一些批话,这会导致后面落座的同学产生压力,或者更加批话。由于你只需要负责吃瓜,所以你希望落座过程中产生的批话程度尽可能大。

落座的过程中有三个指标:

  • ,表示目前的批话程度;
  • ,表示接下来每句话的批话程度增幅;
  • ,表示接下来每个同学落座后 的增幅。

具体而言,当第 位同学坐下时,会发生以下三件事中的一件:

  1. 这位同学发表了一句关于今天的模拟赛成绩的批话,
  2. 这位同学说:“比我后坐的同学都比我强。”,导致后面的同学产生心理负担,
  3. 这位同学沉默不语,气氛突然尴尬,为了活跃气氛,后面的同学的批话程度增幅越来越大,

在每位同学落座之后,

你需要求出 位同学按顺序落座之后,批话程度最大可能是多少,即 的最大值。由于你急着去救轨道上的 6 个人,你需要在 1 秒内算出答案。

输入格式

本题有多组数据。

第一行一个正整数 ,表示测试点编号,以便选手方便地获得部分分。样例中 的含义为数据范围与某个测试点相同。

接下来一行一个正整数 ,表示数据组数。

每组数据第一行一个正整数 ,接下来 行,每行三个非负整数

输出格式

对于每组数据,输出一行一个非负整数 ,表示批话程度的最大值。

样例

样例 1

输入

1
3
2
1 3 2
0 9 9
2
5 3 2
0 9 9
2
2 3 5
3 100 100

输出

3
5
8

样例 2

输入

2
2
3
23 2 6
17 3 5
11 4 2
4
21 9 5
6 7 2
5 11 3
4 5 3

输出

51
48

数据范围与提示

对于所有数据,