配点: 100 点
输入文件较大且语言速度较慢时会出现此问题。满分获取难度较大,请小心。
問題
在天平左侧的板上。 N 硬币从顶部开始垂直堆叠。 1, 硬币 我们称之为 2 , \cdots, 硬币 我们称之为 N 。由于氧化等因素,这些硬币的质量每天都在变化。i 今日硬币 j 的质量是 M_{i,j} 。
你 D 连续几天每天玩以下游戏。
- 将任意数量的硬币从天平左侧的盘子顶部移动到右侧的盘子。 无需移动任何1 棋子。
- 计算平衡天平所需的重物的质量。 G 。G 是左右板上堆放的硬币总质量之差的绝对值。
- 你花费了 支付 G 。
D 编写一个程序,找出一段时间内必须支付的总成本的最小值。
制約
- 1 \leq N \leq 2\,000.
- 1 \leq D \leq 2\,000.
- 1 \leq M_{i,j} \leq 1\,000\,000\,000 (1 \leq i \leq D, 1 \leq j \leq N).
小課題
- (8 点) N = 2.
- (8 点) N = 3.
- (14 点) N \leq 10,D \leq 10.
- (24 点) N \leq 200,D \leq 200.
- (46 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N D
M_{1,1} M_{1,2} ... M_{1,N}
M_{2,1} M_{2,2} ... M_{2,N}
\vdots
M_{D,1} M_{D,2} ... M_{D,N}
出力
在标准输出上, 计算所有带有D 一段时间内必须支付的最低总成本。 1 请按行输出。
入力例 1
3 4 10 8 3 5 7 8 9 6 1 2 8 9
出力例 1
14
如果您执行以下操作,您将支付的总费用将为 14 ,这是最小值。 另外,这个输入示例是 2, 3, 4, 5 满足约束。
- 1 当天硬币 移动 1 页。需要支付的费用 |10 - (8+3)| = 1 。
- 2 当天硬币 移动 1 根本不动。需要支付的费用 |5 - (7+8)| = 10 。
- 3 当天硬币 移动 1 根本不动。需要支付的费用 |9 - (6+1)| = 2 。
- 4 当天硬币 移动 1 页。需要支付的费用 |(2+8) - 9| = 1 。
入力例 2
10 8 50 8 226 426 123 30 114 304 230 994 402 230 316 555 193 95 547 66 171 1000 399 30 24 177 97 325 315 1 361 993 606 973 94 32 391 116 64 782 784 631 759 1000 130 503 81 538 260 41 71 118 1000 148 223 149 113 1 110 366 56 113 1000 245 104 383 171 27 244 34 204 121 55 1000 32 151 59 44 270 386 36 104
出力例 2
6733
此输入示例是一个小作业。 3, 4, 5 满足约束。
入力例 3
1 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
10000000000
此输入示例是一个小作业。 3, 4, 5 满足约束。 输出是 32 请注意,它可能不适合位整数类型。