← 返回题目列表

AtCoder · tenka1_2016_final_e

E. 串烧派对

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

配点 : 900 点

問題文

天海一君是 我准备了 N 块肉。将每块肉水平放置。L厘米×长度1它的形状细长为厘米,L的 您可以创建一个包含1分为厘米见方的部分。肉的硬度是根据每个部位决定的,i从左边的肉 第j部分的硬度为a_{i,j}对于 N肉块从上到下垂直放置,左边缘对齐。

天海一君垂直切了所有的肉。1我正在尝试用书串串起来来制作串肉串。天海一君是

  1. 任何肉类1向左或向右一位k重复移动厘米的操作任意多次。k必须是整数。这时候的费用 需要k^2。然而,同样的肉 移位请勿超过2次。
  2. 移动肉后,将竹签纵向插入某个位置。应该没有不能被串穿的肉。每一块肉,插入串肉串的部分(串肉串足够细,所以1成本等于物体的硬度(假设它刺穿成两部分)。

找到总成本的最小值。

制約

  • 1 ≦ N ≦ 100
  • 1 ≦ L ≦ 10000
  • 1 ≦ a_{i,j} ≦ 10^9

入力

输入是按以下格式从标准输入给出的。

N L
a_{1,1} … a_{i,L}
:
a_{N,1} … a_{N,L}

出力

N求将单块肉串成串所需的最低总成本。


入力例 1

2 3
1 5 6
5 3 1

出力例 1

4

1第二块肉1cm 向右移动,2第二块肉1向左移动厘米,然后1从左边第二块肉开始1如果你将它串起来,使其粘在第二部分上,则转移成本将为1+1,以我刺穿的肉的硬度。 其成本为1+1,因此总计4。成本 没有办法用小于4来串它。


入力例 2

3 4
1 3 5 2
8 3 5 7
3 5 1 4

出力例 2

7

入力例 3

4 5
8 12 20 9 15
5 4 8 15 12
20 18 10 3 9
15 7 13 14 4

出力例 3

25