题目描述

有编号从 $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}$ ；

样例 1

输入

3 4
1 4
2 2 5 1
1 3 3 2
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

输出

20

说明/提示

输入的数字都是整数 $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张券。