問題文

草原に $N$ 本の花が咲いています。
時刻 $0$ の時点では、$i \: (1 \leq i \leq N)$ 個目の花には $B_i$ の美しさがあります。

摘まれていない花は成長し続けているため、美しさが増加し続けます。
具体的には、$i$ 個目の花は時刻 $j \: (1 \leq j \leq N - 1)$ に摘まれていない場合には美しさが瞬間的に $D_{ij}$ だけ増加します。

やきとりくんは、時刻 $0.5$ から、時刻 $1$ ごとに花を $1$ つ以下だけ摘んで花束を作ろうとしています。(選ばなくても良いです。)
また、花束の美しさは、摘んだ花の美しさの合計で定義されます。

時刻 $N$ にやきとりくんが作ることのできる花束の美しさの最大値を求めてください。

制約

• $1 \leq N \leq 200$
• $| B_i | \leq 10^{5}$
• $1 \leq D_{ij} \leq 10^{5}$
• 入力はすべて整数である。

入力

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

出力

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

入出力例

4
1 9 4 -16
5 7 11
2 3 5
3 5 7
3 5 7

47

以下のような手順で美しさ $47$ の花束を作ることができます。

• 時刻 $0.5$ には何もしない。
• 時刻 $1.5$ に $2$ 個目の花を摘む。花束の美しさは $11$ となる。
• 時刻 $2.5$ に $3$ 個目の花を摘む。花束の美しさは $23$ となる。
• 時刻 $3.5$ に $1$ 個目の花を摘む。花束の美しさは $47$ となる。