問題文

体力が $10^{100}$ のモンスターが $1$ 匹います。

あなたは、このモンスターと $N$ ターンのバトルを行います。

$i \: (1 \leq i \leq N)$ ターン目では、以下の行動を順に行います。

• $3$ 種類のカードの中から $1$ 枚選ぶ。$j$ 種類目のカードを選ぶと、$A_{i,j}$ だけ攻撃力が上昇する。ただし、前回のターンで選んだ種類のカードを選ぶことはできない。
• 現在の攻撃力を $x$ とした時に、$x$ ダメージを与える。その直後に攻撃力が $\max(0, x - 1)$ に変化する。

バトルの初めの時点では、あなたの攻撃力は $0$ です。

モンスターに与えることのできるダメージの合計としてあり得る最大値を求めてください。

制約

• $1 \leq N \leq 5000$
• $0 \leq A_{i, j} \leq 10^{9}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

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

出力

問題の答えを一行に出力せよ。

サンプル

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