配点 : $1000$ 点

問題文

$1$ から $N$ までの番号のついた $N$ 軒の焼肉店があります。 焼肉店は番号順に一直線上に並んでいて、$i$ 番目の焼肉店と $i+1$ 番目の焼肉店の距離は $A_i$ です。

joisinoお姉ちゃんは、$1$ から $M$ までの番号のついた $M$ 枚のチケットを持っています。 どの焼肉店でも、これらのチケットと引き換えに焼き肉を食べられます。 $i$ 番目の焼肉店で、$j$ 番目のチケットと引き換えに食べられる焼き肉の美味しさは $B_{i,j}$ です。 一度使ったチケットは $2$ 度以上使えません。 また、同じ焼肉店で使うチケットの数に制限はありません。

joisinoお姉ちゃんは、適当な焼肉店の前からスタートして、別の焼肉店の場所へ移動したり、 目の前にある焼肉店でまだ使っていないチケットを使って焼き肉を食べたりすることを繰り返して、$M$ 枚の焼き肉を食べようとしています。 joisinoお姉ちゃんの最終的な幸福度は、「食べた焼き肉の美味しさの総和 $-$ 移動した距離の合計」で求められます。 joisinoお姉ちゃんの最終的な幸福度の最大値を求めてください。

制約

• 入力は全て整数である
• $2 \leq N \leq 5 \times 10^3$
• $1 \leq M \leq 200$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_{i,j} \leq 10^9$

入力

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

$N$ $M$

$A_1$ $A_2$ $...$ $A_{N-1}$

$B_{1,1}$ $B_{1,2}$ $...$ $B_{1,M}$

$B_{2,1}$ $B_{2,2}$ $...$ $B_{2,M}$

$:$

$B_{N,1}$ $B_{N,2}$ $...$ $B_{N,M}$

出力

joisinoお姉ちゃんの最終的な幸福度の最大値を出力せよ。

3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1

11

$1$ 番目の焼肉店の前からスタートし、$1$ 番目と $3$ 番目のチケットを使って焼き肉を食べたあと、 $2$ 番目の焼肉店の前まで移動して、$2$ 番目と $4$ 番目のチケットを使って焼き肉を食べると、幸福度を最大化できます。

5 3
1 2 3 4
10 1 1
1 1 1
1 10 1
1 1 1
1 1 10

20