← 返回题目列表

AtCoder · arc067_d

F. 烤肉餐厅

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有 N 沿街的烧烤店。 餐厅都有编号 1 通过 N 从西到东,以及餐厅之间的距离 i 和餐厅 i+1 is A_i.

Joisino 有 M 门票,编号 1 通过 M。 每家烧烤店都提供烧烤餐,需要换取这些门票。 餐厅 i 提供一顿饭 美味 B_{i,j} 换取门票 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