Description

注意：此题与上一题的题面完全相同，只有数据范围有差别。

$\mathcal{PinkRabbit}$ 在 $\texttt{F}$ 市的主干道找到了妹子之后，他意识到车来车往人头攒动的主干道不是一个合适的约会地点。于是 $\mathcal{PinkRabbit}$ 与妹子来到了一条充满情调的林荫小径上。$\mathcal{PinkRabbit}$ 发现，这里每隔几米就是一家咖啡馆，于是他认为这里是一个很好的约会地点。

由于不熟悉每家咖啡馆的饮品的美味程度，$\mathcal{PinkRabbit}$ 对今天他与妹子喝的饮品并不是很满意。一周过去了，$\mathcal{PinkRabbit}$ 与妹子再次回到了这个地方，而这个时候 $\mathcal{PinkRabbit}$ 早已做好万全的准备，他发誓要让他与他的妹子度过完美的一天。

经过 $\mathcal{PinkRabbit}$ 长时间的深入调查，他统计出这条小径上总共有 $n$ 家咖啡馆，从左到右编号依次为 $1,2,\cdots,n$。可以认为这些咖啡馆分布在一条直线上。第 $i$ 家咖啡馆到第 $i+1$ 家咖啡馆的距离为 $d_{i}$。每家咖啡馆都有 $m$ 种主打饮品。$\mathcal{PinkRabbit}$ 认为妹子对第 $i$ 家咖啡馆的第 $j$ 种饮品的喜爱程度为 $w_{i,j}$。

$\mathcal{PinkRabbit}$ 有足够的资金支持，他可以在任意一家咖啡馆点任意一种饮品任意多份。可惜的是，今天每家咖啡馆的每种饮品只供应一份。又由于任意两家咖啡馆的编号相同的饮品配方是类似的，所以 $\mathcal{PinkRabbit}$ 不希望在两家不同的咖啡馆点两种编号相同的饮品。

$\mathcal{PinkRabbit}$ 与妹子乘坐着「 The Knight 」来到了这条小径，他们可以在这条小径的任意一处下车，然后前往任意一家咖啡馆约会，并在这家咖啡馆点任意种饮品品尝。在一家咖啡馆约会完毕后，他们还可以再去任意一家咖啡馆（包括已经在其中约过会的咖啡馆）约会和品尝饮品。因为毕竟距离不远，并且和妹子散步是一件很开心的事情，所以$PinkRabbit$决定安步当车，步行前往下一家咖啡馆。最后当 $\mathcal{PinkRabbit}$ 决定结束约会后，他可以命令「 The Knight 」行驶到当前位置并接 $\mathcal{PinkRabbit}$ 和妹子上车。

因为 $\mathcal{PinkRabbit}$ 优先考虑妹子对饮品的满意程度，并且 $\mathcal{PinkRabbit}$ 和妹子都不喜欢走路，于是 $\mathcal{PinkRabbit}$ 定义这次约会的成功程度为妹子对于品尝过的饮品的满意程度之和减去他们步行的距离之和。

由于 $\mathcal{PinkRabbit}$ 忙着选定再下一次约会的地点，没空计算这次的约会的成功程度，所以请你帮他设计程序计算这次约会的成功程度的最大值。

Input Format

从文件 date.in 中读入数据。

首先是两个正整数 $n$ 和 $m$，分别表示这条小径上的咖啡馆数量和每家咖啡馆供应的饮品种类。
接下来一行 $n-1$ 个正整数 $d_1,d_2,\cdots,d_{n-1}$，表示相邻两个咖啡馆之间的距离。
接下来 $n$ 行，第 $i$ 行有 $m$ 个数 $w_{i,1},w_{i,2},\cdots,w_{i,m}$，表示妹子对第 $i$ 家咖啡馆的 $m$ 种饮品的喜爱程度。

Output Format

输出到文件 date.out 中。

输出一行一个数，表示这次约会的成功程度的最大值。

Sample

样例输入 1

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

样例输出 1

11

样例解释 1

$\mathcal{PinkRabbit}$ 与妹子采用如下策略：在第 $2$ 家咖啡馆处下车，进入第 $2$ 家咖啡馆，并品尝第 $2$ 和第 $4$ 种饮品，然后步行前往第 $1$ 家咖啡馆，并在第 $1$ 家咖啡馆品尝第 $1$ 和第 $3$ 种饮品。约会的成功程度为 $(3+2+2+5)-1=11$。

样例输入 2

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

样例输出 2

20

样例输入 3

10 5
3 4 6 7 3 7 7 7 6
12 34 8 33 10
6 38 34 6 20
18 5 19 20 24
18 28 34 22 7
14 10 19 39 8
18 9 8 17 31
12 40 15 38 5
24 27 31 14 9
14 39 18 24 6
37 34 38 8 30

样例输出 3

答案请手动计算。

Hint

Subtask #6 $(60\;pts)$：$1\le n\le 10^5$，$1\le m\le 10$。
Subtask #7 $(40\;pts)$：$n=m=1$，$w_{1,1}=0$；即输出 0 就可获得此子任务的分数。
对于所有数据，均有 $n\times m\le 10^6$，$1\le d_i, w_{i,j}\le 10^9$。

注： Subtask #7 的作用是削减此题的满分分数到 60 分。

出题人：PinkRabbit/TibbarKniper。