题目描述

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

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

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

输入格式

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

$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お姉ちゃんの最終的な幸福度の最大値を出力せよ。

题目大意

题目描述

有编号从 $1$ 到 $N$ 的 $N$ 家烧烤店，烧烤店在一条线上按照编号顺序排序，第 $i$ 家烧烤店与第 $i + 1$ 家烧烤店的距离是 $A_i$ 。
你有编号从 $1$ 到 $M$ 的 $M$ 张烧烤券，不管是在哪一家烧烤店都可用烧烤券来吃烧烤，在第 $i$ 家烧烤店用烧烤券 $j$ 可以吃到一顿美味度为 $B_{i,j}$ 的烧烤，每一张烧烤券只能使用一次，但是在一家烧烤店你可以使用任意多张烧烤券。
你想从自己选择的一家烧烤店开始（随意选择一个开始），然后不断地用未使用的烧烤券去另一家烧烤店。你最终的幸福值是所吃所有烧烤的美味度减去所走的总路程。求最大可能的最终幸福值（ $M$ 张券必须用完）。

输入输出格式

输入格式 第一行两个整数 $N$ , $M$ ; 第二行有 $N - 1$ 个整数， $A_1 , A_2 , ... , A_{n-1}$ ； 接下来的 $N$ 行，每行 $M$ 个整数，第 $i$ 行第 $j$ 列的整数是 $B_{i,j}$ ；

说明

数据范围： 输入的数字都是整数 $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$ 样例解释： 样例1： 在第一家烧烤店开始，使用第1张和第3张券，然后去第二家烧烤店，使用第2张和第4张券。

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

11

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

20

提示

制約

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

Sample Explanation 1

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