Problem Statement

There is $1$ monster with $10^{100}$ health.

You will fight this monster in a battle of $N$ turns.

On turn $i \: (1 \leq i \leq N)$, you perform the following actions in order.

• Choose $1$ card from $3$ types of cards. If you choose the card of type $j$, your attack power increases by $A_{i,j}$. However, you cannot choose the card of the same type as the one you chose on the previous turn.
• Let $x$ be your current attack power. You deal $x$ damage. Immediately after that, your attack power changes to $\max(0, x - 1)$.

At the start of the battle, your attack power is $0$.

Find the maximum possible total damage you can deal to the monster.

Constraints

• $1 \leq N \leq 5000$
• $0 \leq A_{i, j} \leq 10^{9}$
• All inputs are integers.

Input

The input is given from standard input in the following format.

$N$
$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $A_{N,3}$

Output

Output the answer to the problem on one line.

Sample

3
1 3 1
4 10 2
7 12 5

27

5
0 0 0
0 8 0
0 0 0
0 0 0
0 0 0

26