시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 2048 MB1000.000%

문제

Дана таблица $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$ после применения всех операций.

서브태스크

번호배점제한
115

$r + c \le 14$

218

$ r \cdot c \le 500 $

35

Все строки и столбцы отсортированы в возрастающем порядке и $ r \cdot c \le 250\,000 $

47

$r = 1$, $ r \cdot c \le 250\,000 $

56

$r \le 2$, $ r \cdot c \le 250\,000 $

62

$r \le 20 $, $ r \cdot c \le 250\,000 $

710

$r,\ c \le 100$

82

$r \cdot c \le 10\,000$

91

$r \le 100$, $c \le 1000$

101

$r \le 100$, $c \le 2500$

111

$r \le 100$, $c \le 5000$

121

$r \le 100$, $c \le 7500$

131

$r \le 100$, $c \le 10\,000$

144

$r \le 100$, $c \le 15\,000$

152

$r \le 100$, $c \le 20\,000$

163

$r,\ c \le 200$

173

$r,\ c \le 400$

184

$r,\ c \le 600$

191

$r,\ c \le 800$

201

$r,\ c \le 1000$

211

$r,\ c \le 1200$

221

$r,\ c \le 1400$

231

$r \cdot c \le 100\,000$

241

$r \cdot c \le 250\,000$

254

$r \cdot c \le 500\,000$

261

$r \cdot c \le 750\,000$

271

$r \cdot c \le 1\,000\,000$

281

$r \cdot c \le 1\,500\,000$

291

예제 입력 1

2 3
3 4 1
5 6 2

예제 출력 1

6

예제 입력 2

2 3
2 3 4
1 6 5

예제 출력 2

2

노트

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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.