AT_arc067_d [ARC067F] Yakiniku Restaurants

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

第一行两个整数 $ 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 $。