ストーリー

やきとりくんは、完成したパンを友人たちで食べることにしましたが、 パンは冷めると美味しくなくなってしまうため、どのような順番で食べると良いかを考えることにしました。

問題文

$N$ 個のパンがあります。 時刻 $0$ の時点では、$i \: (1 \leq i \leq N)$ 本目のパンを食べると $A_i$ の幸福度を得ることができます。
しかし、$i$ 本目のパンは時刻 $j \: (1 \leq j \leq N - 1)$ に、得られる幸福度が瞬間的に $B_{ij}$ だけ低下します。
やきとりくんは、時刻 $0.5$ から、時刻 $1$ ごとにパンを $1$ 個だけ食べることができます。(食べなくても良いです。)

時刻 $N$ にやきとりくんが得られる幸福度の最大値を求めてください。

制約

• $1 \leq N \leq 16$
• $1 \leq A_{i} \leq 10^{9} \: (1 \leq i \leq N)$
• $1 \leq B_{ij} \leq 10^{9} \: (1 \leq j \leq N - 1)$
• 入力はすべて整数である。

入力

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

N
A1 A2 ...... AN
B11 B12 ...... B1 N-1
B21 B22 ...... B2 N-1
......
BN1 BN2 ...... BN N-1

出力

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

入出力例

3
7 9 12
2 3
4 2
3 4

20

$2$ 番目のパン、$3$ 番目のパン、$1$ 番目のパンの順に食べると、$9 + 9 + 2 = 20$ の幸福度を得ることが可能です。

2
9 24
1000
1000

24

初めに $2$ 番目のパンを食べて、時刻 $1.5$ にはパンを食べないことによって $24$ の幸福度を得ることが可能です。