给定一个 $r$ 行 $c$ 列的表格 $a$，其中包含 $1$ 到 $r \cdot c$ 的所有不同数字，且排列顺序任意。这些表格元素将被转移到一个初始为空的数组 $b$ 中。在表格非空时，可以对其执行以下两种操作之一：
- 将表格第一行的元素按从第一列到最后一列的顺序追加到数组 $b$ 的末尾，并从表格中删除第一行。
- 将表格第一列的元素按从第一行到最后一行的顺序追加到数组 $b$ 的末尾，并从表格中删除第一列。
要求选择操作顺序，使得在执行完所有操作后，所得数组 $b$ 中的逆序对数量最少。
逆序对定义为数组中满足 $1 \leqslant i < j \leqslant r \cdot c$ 且 $b_i > b_j$ 的下标对 $(i, j)$。
输入格式
第一行包含两个整数 $r$ 和 $c$ ($r \leqslant c, 1 \leqslant r \cdot c \leqslant 2\,000\,000$)，分别表示表格的行数和列数。
接下来的 $r$ 行描述表格 $a$。第 $i$ 行包含 $c$ 个整数 $a_{i1}, \dots, a_{ic}$ ($1 \leqslant a_{ij} \leqslant r \cdot c$)，表示矩阵 $a$ 的元素。
保证表格 $a$ 中的所有数字各不相同。
输出格式
输出一个整数，表示执行所有操作后数组 $b$ 中可能的最少逆序对数量。
子任务
| 子任务 | 分值 | 约束条件 | 依赖子任务 |
|---|---|---|---|
| 1 | 15 | $r + c \leqslant 14$ | |
| 2 | 18 | $r \cdot c \leqslant 500$ | 1 |
| 3 | 5 | 所有行和列均升序排列，$r \cdot c \leqslant 250\,000$ | |
| 4 | 7 | $r = 1, r \cdot c \leqslant 250\,000$ | |
| 5 | 6 | $r \leqslant 2, r \cdot c \leqslant 250\,000$ | 4 |
| 6 | 2 | $r \leqslant 20$ | 1, 4, 5 |
| 7 | 10 | $r, c \leqslant 100$ | 1 |
| 8 | 2 | $r \cdot c \leqslant 10\,000$ | 1, 2, 7 |
| 9 | 1 | $r \leqslant 100, c \leqslant 1000$ | 1, 2, 7 |
| 10 | 1 | $r \leqslant 100, c \leqslant 2500$ | 1, 2, 7, 9 |
| 11 | 1 | $r \leqslant 100, c \leqslant 5000$ | 1, 2, 7, 9, 10 |
| 12 | 1 | $r \leqslant 100, c \leqslant 7500$ | 1, 2, 7, 9–11 |
| 13 | 1 | $r \leqslant 100, c \leqslant 10\,000$ | 1, 2, 7–12 |
| 14 | 4 | $r \leqslant 100, c \leqslant 15\,000$ | 1, 2, 7–13 |
| 15 | 2 | $r \leqslant 100, c \leqslant 20\,000$ | 1, 2, 7–14 |
| 16 | 3 | $r, c \leqslant 200$ | 1, 7 |
| 17 | 3 | $r, c \leqslant 400$ | 1, 7, 16 |
| 18 | 4 | $r, c \leqslant 600$ | 1, 2, 7, 16, 17 |
| 19 | 1 | $r, c \leqslant 800$ | 1, 2, 7, 16–18 |
| 20 | 1 | $r, c \leqslant 1000$ | 1, 2, 7, 9, 16–19 |
| 21 | 1 | $r, c \leqslant 1200$ | 1, 2, 7, 9, 16–20 |
| 22 | 1 | $r, c \leqslant 1400$ | 1, 2, 7, 9, 16–21 |
| 23 | 1 | $r \cdot c \leqslant 100\,000$ | 1, 2, 7–9, 16 |
| 24 | 1 | $r \cdot c \leqslant 250\,000$ | 1–10, 16, 17, 23 |
| 25 | 4 | $r \cdot c \leqslant 500\,000$ | 1–11, 16–18, 23, 24 |
| 26 | 1 | $r \cdot c \leqslant 750\,000$ | 1–12, 16–19, 23–25 |
| 27 | 1 | $r \cdot c \leqslant 1\,000\,000$ | 1–13, 16–20, 23–26 |
| 28 | 1 | $r \cdot c \leqslant 1\,500\,000$ | 1–14, 16–21, 23–27 |
| 29 | 1 | 无额外限制 | 1–28 |
样例
输入格式 1
2 3 3 4 1 5 6 2
输出格式 1
6
说明
在第一个样例中，通过两次删除第一行可以达到最少逆序对数量。结果数组 $b$ 为 $[3, 4, 1, 5, 6, 2]$，该数组包含 $6$ 个逆序对。
输入格式 2
2 3 2 3 4 1 6 5
输出格式 2
2
说明
在第二个样例中，为了达到最少逆序对数量，可以先删除第一列，然后两次删除第一行。结果数组 $b$ 为 $[2, 1, 3, 4, 6, 5]$，该数组包含 $2$ 个逆序对。