题目描述

一条街上有$N$家烧烤餐厅，从西到东依次编号为$1$到$N$，第$i$家餐厅与第$i+1$家餐厅的距离是$A_i$。

Joisino有$M$张票，分别编号为$1$到$M$。每家烧烤餐厅都可以用这些票换取美食。第$i$家餐厅用票$j$换取的美食“美味度”是$B_{i,j}$。每张票只能使用一次，但可以在一家餐厅使用任意张票。

Joisino想要通过选择一家餐厅开始，然后反复前往另一家烧烤餐厅，并在当前位置的餐厅使用未使用的票券，来享受$M$顿烧烤。最终，她的“幸福感”可以通过以下公式计算：“（所吃美食的总美味度）-（所走的总路程）”。找出她可能的最大“幸福感”。

约束条件

• 所有输入值均为整数。
• $2≤N≤5×10^3$
• $1≤M≤200$
• $1≤A_i≤10^9$
• $1≤B_{i,j}≤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可能的最大“幸福感”。

示例输入 1

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

示例输出 1

11

可以通过以下策略将最大化“幸福感”：从餐厅$1$开始，使用票$1$和$3$，然后前往餐厅$2$并使用票$2$和$4$。

示例输入 2

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

示例输出 2

20