题目描述

Prof. Pang has $3$ different skills to practice, including soda drinking, fox hunting, and stock investing. We call them Skill $1$, Skill $2$, and Skill $3$. In each of the following $n$ days, Prof. Pang can choose one of the three skills to practice. In the $i$-th day ($1\le i\le n$), if Prof. Pang chooses Skill $j$ ($1\le j\le 3$) to practice, his level of Skill $j$ will increase by $a_{i,j}$. Initially, Prof. Pang's levels of all skills are $0$.

Prof. Pang forgets skills if he does not practice. At the end of each day, if he has not practiced Skill $j$ for $k$ days, his level of Skill $j$ will decrease by $k$. For example, if he practices Skill $1$ on day $1$ and Skill $2$ on day $2$, at the end of day $2$, he has not practiced Skill $1$ for $1$ day and has not practiced Skill $3$ for $2$ days. Then his levels of Skill $1$ and Skill $3$ will decrease by $1$ and $2$, respectively. His level of Skill $2$ does not decrease at the end of day $2$ because he practices Skill $2$ on that day. In this example, we also know that his levels of Skill $2$ and Skill $3$ both decrease by $1$ at the end of day $1$.

Prof. Pang's level of any skill will not decrease below $0$. For example, if his level of some skill is $3$ and at the end of some day, this level is decreased by $4$, it will become $0$ instead of $-1$.

Prof. Pang values all skills equally. Thus, he wants to maximize the sum of his three skill levels after the end of day $n$.

Given $a_{i,j}$ ($1\le i\le n, 1\le j\le 3$), find the maximum sum.

输入格式

The first line contains a single integer $T~(1 \le T \le 1000)$ denoting the number of test cases.

For each test case, the first line contains an integer $n~(1 \le n \le 1000)$. The $(i+1)$-th line contains three integers $a_{i,1}, a_{i,2}, a_{i,3}$ ($0\le a_{i,j}\le 10000$ for any $1\le i\le n, 1\le j\le 3$).

It is guaranteed that the sum of $n$ over all test cases is no more than $1000$.

输出格式

For each test case, output the maximum possible sum of skill levels in one line.

题目大意

题目描述。

庞博士有 $3$ 项技能：喝汽水、猎狐和炒股，编号分别为 $1,2,3$。初始时，每项技能的熟练度为 $0$。

接下来有 $n$ 天。在第 $i$ 天，庞博士可以选择一项技能（假设是第 $j$ 项）进行练习，然后在这天结束时让这项技能的熟练度增加 $a_{i,j}$。同时，如果某一项技能（假设是第 $k$ 项）已经有 $x$ 天没有练习，那么在这天结束时，这项技能的熟练度会减少 $x$。当然，任何一项技能的熟练度都不可能小于 $0$。

现在，庞博士想知道：在第 $n$ 天结束后，这 $3$ 项技能的熟练度之和最大为多少。由于他非常忙，而且他的日程和对习惯的适应程度可能有变，所以庞博士把这 $T$ 个问题交给了你——每个问题的内容都一样，只是给出的数据可能有所不同而已。

输入格式

第一行，一个正整数 $T~(1 \leq T \leq 1000)$，表示数据组数。

对于每组数据，输入 $(n + 1)$ 行。

• 第一行，一个正整数 $n~(1 \leq n \leq 1000)$，表示天数。

• 接下来 $n$ 行，每行 $3$ 个非负整数，表示题目描述中的 $a_{i,j}~(1 \leq i \leq n,1 \leq j \leq 3,0 \leq a_{i,j} \leq 10000)$。

输出格式

对于每组数据，输出 $1$ 行 $1$ 个数，表示答案。

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

26
41