Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
Statistics

还有不到 1000 个星期就要高考了!为了帮你刚出生的学弟备战高考,你决定帮他制定一个训练计划。

在每个星期,他可以选择数竞、物竞、文化课中的一个进行训练,分别记为课程 $1,2,3$ 。如果在第 $i$ 个星期选择了第 $j$ 门课程,他在第 $j$ 门课程的水平就会提高 $a_{i,j}$ 。初始三门课程的水平都是 $0$ 。

一门课程太久没学就会水平下降。在每个星期结束的时候,如果他已经连续 $k$ 个星期(包括这个星期)没有学习第 $j$ 门课程了,那么他在第 $j$ 门课程的水平就会下降 $k$ 。比如他某三个星期分别学习了 $3,1,2$ ,那么在第三个星期结束时第 $1$ 门课程的水平会下降 $1$ ,而第 $3$ 门课程的水平会下降 $2$ 。特别的,单门课的水平不会降到 $0$ 以下。

你希望你的学弟全面发展,所以你希望最大化他在高考时三门课程的水平之和。

输入格式

第一行一个正整数 $T$ ,表示数据组数。每组数据的格式如下:

  • 第一行一个正整数 $n$ ,表示距离高考还有几个星期。
  • 接下来 $n$ 行,每行三个非负整数 $a_{i,1},a_{i,2},a_{i,3}$ .

输出格式

对每组数据输出一行一个非负整数,表示答案。

样例 1

input

2
3
1 1 10
1 10 1
10 1 1
5
1 2 3
6 5 4
7 8 9
12 11 10
13 14 15

output

26
41

样例 2

见下发文件。

数据范围

对于所有数据,保证 $1\le T\le 1000,1\le n,\sum n\le 1000,0\le a_{i,j}\le 10^4$ 。

子任务编号 $\sum n\le $ $a_{i,j}\le $ 特殊性质 分值
$1$ $200$ $ $ / $20$
$2$ $ $ $ $ $a_{i,j}$ 在范围内随机生成 $25$
$3$ $800$ $10^3$ / $25$
$4$ $ $ $ $ / $30$

时间限制:$\texttt{2s}$

空间限制:$\texttt{1024MB}$