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

天海一君垂直切了所有的肉。1我正在尝试用书串串起来来制作串肉串。天海一君是
- 任何肉类1向左或向右一位k重复移动厘米的操作任意多次。k必须是整数。这时候的费用 需要k^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