Минимизация инверсий

Дана таблица $a$, состоящая из $r$ строк и $c$ столбцов, в которой записаны в произвольном порядке все различные числа от $1$ до $r \cdot c$. Элементы этой таблицы переносятся в изначально пустой массив $b$.

Пока таблица непустая, над ней выполняется одно из двух действий:

• Дописать в конец массива элементы первой строки таблицы в порядке от элемента в первом столбце до элемента в последнем и удалить первую строку из таблицы.

• Дописать в конец массива элементы первого столбца таблицы в порядке от элемента в первой строке до элемента в последней и удалить первый столбец из таблицы.

Порядок действий требуется выбирать таким, чтобы количество инверсий в полученном массиве после применения всех операций было минимальным.

Инверсией называется такая пара индексов элементов массива $1 \le i < j \le r\cdot c$, что $b_i > b_j$.

Первая строка содержит два целых числа $r$ и $c$ ($r \le c$, $1 \le r \cdot c \le 2\,000\,000$) --- количество строк и столбцов в таблице соответственно.

В следующих $r$ строках содержится описание таблицы $a$. В $i$-й из них содержится $c$ целых чисел $a_{i1}$, $\ldots$, $a_{ic}$ ($1 \le a_{ij} \le r \cdot c$) --- элементы матрицы $a$.

Гарантируется, что все числа в таблице $a$ различны.

Выведите одно число --- минимально возможное количество инверсий в массиве $b$ после применения всех операций.

В первом примере минимальное число инверсий достигается при двукратном удалении первой строки. В результате массив $b$ будет равен $[3, 4, 1, 5, 6, 2]$. Такой массив содержит $6$ инверсий.

Во втором примере для достижения минимального числа инверсий можно сначала удалить первый столбец, а потом два раза удалить первую строку. В результате массив $b$ будет равен $[2, 1, 3, 4, 6, 5]$. Такой массив содержит $2$ инверсии.