AT_otemae2019_f.天秤とコイン (Balance and Coins)

天平的左侧托盘上竖直堆放着 $N$ 枚硬币，从上到下依次称为硬币 $1$、硬币 $2$、$\cdots$、硬币 $N$。这些硬币由于氧化等原因，每天的质量都会发生变化。第 $i$ 天第 $j$ 枚硬币的质量为 $M_{i,j}$。

你将在 $D$ 天内，每天进行如下操作：

• 可以将天平左侧托盘上从上往下任意数量的硬币移动到右侧托盘上。也可以一枚都不移动。
• 设天平两侧托盘上硬币总质量的差的绝对值为 $G$，即 $G = |\text{左侧总质量} - \text{右侧总质量}|$。
• 你需要支付 $G$ 的代价。

请编写程序，求出 $D$ 天内你需要支付的总代价的最小值。

输入以如下格式从标准输入读入：

$N$ $D$ $M_{1,1}$ $M_{1,2}$ $\cdots$ $M_{1,N}$ $M_{2,1}$ $M_{2,2}$ $\cdots$ $M_{2,N}$ $\vdots$ $M_{D,1}$ $M_{D,2}$ $\cdots$ $M_{D,N}$

请输出 $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$。

子任务

1. ($8$ 分) $N = 2$。
2. ($8$ 分) $N = 3$。
3. ($14$ 分) $N \leq 10$，$D \leq 10$。
4. ($24$ 分) $N \leq 200$，$D \leq 200$。
5. ($46$ 分) 无额外约束。

样例解释 1

按照如下方式操作时，总代价为 $14$，且这是最小值。该输入样例满足子任务 $2, 3, 4, 5$ 的约束。

• 第 $1$ 天移动 $1$ 枚硬币。代价为 $|10 - (8+3)| = 1$。
• 第 $2$ 天一枚硬币都不移动。代价为 $|5 - (7+8)| = 10$。
• 第 $3$ 天一枚硬币都不移动。代价为 $|9 - (6+1)| = 2$。
• 第 $4$ 天移动 $1$ 枚硬币。代价为 $|(2+8) - 9| = 1$。

样例解释 2

该输入样例满足子任务 $3, 4, 5$ 的约束。

样例解释 3

该输入样例满足子任务 $3, 4, 5$ 的约束。注意输出可能超出 $32$ 位整数范围。

由 ChatGPT 4.1 翻译