AT_arc018_3.[ARC018C] 席替え

我所在的学校每个班级的人数特别多，甚至有多达 $1,000,000$ 人的班级。我的班级也不例外。教室的座位排成 $N$ 行 $M$ 列的矩形，共有 $N \times M$ 名学生，每人拥有一张自己的桌子。

学校非常重视防灾意识，如果发生意外，教室后面的墙壁可以打开，让学生从这里避难。最近，学校决定让成绩好的学生优先撤离，所以我们班决定重新安排座位，让成绩好的学生坐得更靠后。具体来说，把最前面的一行称为第 $0$ 行，最左边的一列称为第 $0$ 列。位于第 $i$ 行第 $j$ 列的座位用 $(i, j)$ 表示，坐在这个位置的学生成绩用 $G[i][j]$ 表示。对于任意两个座位 $(a, b)$ 和 $(c, d)$，如果 $a > c$，则无论 $b, d$ 的值如何，必须满足 $G[a][b] \geq G[c][d]$。

学生可以自由移动到任意座位，但是不能有两个或更多学生坐在同一座位，也不能有空位。同时，桌子数量不能改变，仍保持 $N$ 行 $M$ 列的布局。

重新安排座位是好事，但由于人数众多，我们希望尽量减少所有学生移动的总距离。这里的移动距离是指从原座位到新座位的曼哈顿距离，即如果一个学生从 $(a, b)$ 移动到 $(c, d)$，则移动距离为 $|a - c| + |b - d|$。

给定所有学生在重新安排前的成绩数据，请计算所有学生的最小移动距离总和。

输入格式

• 第一行包含两个整数 $N$ 和 $M$，分别表示教室的行数和列数（$1 \le N, M \le 1,000$）。
• 第二行包含三个整数 $x_0$、$a$ 和 $p$，用来生成每位学生的初始成绩（$0 \le x_0, a \le 10^9$，$N \times M \le p \le 10^9$，$p$ 必为素数）。初始成绩通过递归式 $x_i = (x_{i-1} + a) \mod p$ 生成。在位置 $(i, j)$ 的学生成绩为 $x_{i \times M + j}$。

输出格式

输出所有学生移动距离最小总和。最后包括一个换行符。

数据范围和提示

• $1 \le N, M \le 1,000$
• $0 \le x_0, a \le 10^9$
• $N \times M \le p \le 10^9$ 且 $p$ 为素数

示例

输入

2 3
1 2 59

输出

0

解释

重新安排座位前，学生的成绩如下：

1  3  5
7  9 11

各座位在自己后面（屏幕下方）没有比自己成绩更差的学生，因此无需重新安排。

输入

2 3
6 55 59

输出

2

解释

重新安排座位前，学生的成绩如下：

6  2 57
53 49 45

交换座位 $(0, 2)$ 和 $(1, 2)$ 的学生即可。两者分别移动 1 个单位，总移动距离为 2。

输入

4 5
15 25 79

输出

26

解释

重新安排座位前，学生的成绩如下：

15 40 65 11 36
61  7 32 57  3
28 53 78 24 49
74 20 45 70 16

符合条件的重新安排如：

15  7 16 11  3
28 20 32 24 36
53 40 45 57 49
74 61 65 70 78

本翻译由 AI 自动生成