AT_arc067_d [ARC067F] Yakiniku Restaurants

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

无

无

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