You are given a table $a$ consisting of $r$ rows and $c$ columns, containing all distinct numbers from $1$ to $r \cdot c$ in an arbitrary order. The elements of this table are moved into an initially empty array $b$. While the table is not empty, one of two actions is performed on it:
- Append the elements of the first row of the table to the end of the array in order from the element in the first column to the element in the last column, and remove the first row from the table.
- Append the elements of the first column of the table to the end of the array in order from the element in the first row to the element in the last row, and remove the first column from the table.
The order of actions must be chosen such that the number of inversions in the resulting array after applying all operations is minimized.
An inversion is a pair of indices of array elements $1 \le i < j \le r \cdot c$ such that $b_i > b_j$.
Input
The first line contains two integers $r$ and $c$ ($r \le c$, $1 \le r \cdot c \le 2\,000\,000$) — the number of rows and columns in the table, respectively.
The next $r$ lines contain the description of table $a$. The $i$-th of these lines contains $c$ integers $a_{i1}, \dots, a_{ic}$ ($1 \le a_{ij} \le r \cdot c$) — the elements of matrix $a$.
It is guaranteed that all numbers in table $a$ are distinct.
Output
Output a single number — the minimum possible number of inversions in array $b$ after applying all operations.
Scoring
| Subtask | Points | Constraints | Dependencies |
|---|---|---|---|
| 1 | 15 | $r + c \le 14$ | U |
| 2 | 18 | $r \cdot c \le 500$ | U, 1 |
| 3 | 5 | All rows and columns are sorted in ascending order and $r \cdot c \le 250\,000$ | |
| 4 | 7 | $r = 1$, $r \cdot c \le 250\,000$ | |
| 5 | 6 | $r \le 2$, $r \cdot c \le 250\,000$ | 4 |
| 6 | 2 | $r \le 20$ | U, 1, 4, 5 |
| 7 | 10 | $r, c \le 100$ | U, 1 |
| 8 | 2 | $r \cdot c \le 10\,000$ | U, 1, 2, 7 |
| 9 | 1 | $r \le 100, c \le 1000$ | U, 1, 2, 7 |
| 10 | 1 | $r \le 100, c \le 2500$ | U, 1, 2, 7, 9 |
| 11 | 1 | $r \le 100, c \le 5000$ | U, 1, 2, 7, 9, 10 |
| 12 | 1 | $r \le 100, c \le 7500$ | U, 1, 2, 7, 9–11 |
| 13 | 1 | $r \le 100, c \le 10\,000$ | U, 1, 2, 7–12 |
| 14 | 4 | $r \le 100, c \le 15\,000$ | U, 1, 2, 7–13 |
| 15 | 2 | $r \le 100, c \le 20\,000$ | U, 1, 2, 7–14 |
| 16 | 3 | $r, c \le 200$ | U, 1, 7 |
| 17 | 3 | $r, c \le 400$ | U, 1, 7, 16 |
| 18 | 4 | $r, c \le 600$ | U, 1, 2, 7, 16, 17 |
| 19 | 1 | $r, c \le 800$ | U, 1, 2, 7, 16–18 |
| 20 | 1 | $r, c \le 1000$ | U, 1, 2, 7, 9, 16–19 |
| 21 | 1 | $r, c \le 1200$ | U, 1, 2, 7, 9, 16–20 |
| 22 | 1 | $r, c \le 1400$ | U, 1, 2, 7, 9, 16–21 |
| 23 | 1 | $r \cdot c \le 100\,000$ | U, 1, 2, 7–9, 16 |
| 24 | 1 | $r \cdot c \le 250\,000$ | U, 1–10, 16, 17, 23 |
| 25 | 4 | $r \cdot c \le 500\,000$ | U, 1–11, 16–18, 23, 24 |
| 26 | 1 | $r \cdot c \le 750\,000$ | U, 1–12, 16–19, 23–25 |
| 27 | 1 | $r \cdot c \le 1\,000\,000$ | U, 1–13, 16–20, 23–26 |
| 28 | 1 | $r \cdot c \le 1\,500\,000$ | U, 1–14, 16–21, 23–27 |
| 29 | 1 | U, 1–28 |
Examples
Input 1
2 3 3 4 1 5 6 2
Output 1
6
Note
In the first example, the minimum number of inversions is achieved by removing the first row twice. As a result, the array $b$ will be $[3, 4, 1, 5, 6, 2]$. This array contains 6 inversions.
Input 2
2 3 2 3 4 1 6 5
Output 2
2
Note
In the second example, to achieve the minimum number of inversions, one can first remove the first column, and then remove the first row twice. As a result, the array $b$ will be $[2, 1, 3, 4, 6, 5]$. This array contains 2 inversions.