410684: GYM104076 J Skills

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.

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