Задача №114785. Перемещение клеток
Маленькой девочке Алисе на день рождения подарили современную пиксельную картину.
Картина представляет собой клетчатую прямоугольную таблицу размером \(n\times m\). Известно, что в каждом столбце этой таблицы несколько клеток подряд покрашены в черный цвет, а все остальные клетки — белые.
Алиса считает картину красивой , если существует путь между любыми двумя черными клетками \(u\) и \(v\), который проходит только по черным клеткам, каждый раз переходя из клетки в соседнюю с ней по стороне — начать движение в черной клетке \(u\), затем перейти в соседнюю с \(u\) по стороне черную клетку \(w\), затем перейти в соседнюю с \(w\) по стороне черную клетку, и так далее, добравшись в итоге до черной клетки \(v\).
Так как картина современная, её можно менять. За одно действие разрешается выбрать на ней любой столбец и сдвинуть все черные клетки в этом столбце на одну клетку в одном и том же направлении — вверх или вниз. Клетки можно перемещать, только если они не выходят за границы картины.
Алиса заинтересовалась, какое минимальное количество действий необходимо сделать, чтобы картина стала красивой .
В первой строке ввода даны два целых числа \(n\) и \(m\) — количество строк и количество столбцов у клетчатой картины соответственно (\(1 \leqslant n, m \leqslant 100\,000\)). Гарантируется, что площадь картины не превышает \(10^{6}\) (\(1 \leqslant n \cdot m \leqslant 1\,000\,000\)).
В следующих \(m\) строках записаны по два целых числа \(s_i\) и \(t_i\) — номера начальной и конечной позиции непрерывного отрезка черных клеток в \(i\)-м столбце клетчатой картины (\(1 \leqslant s_i \leqslant t_i \leqslant n\)).
Выведите единственное целое число — минимальное количество действий, которое необходимо сделать с картиной, сделать её красивой .
9 3 1 2 4 5 7 9
4