0htoAi 的至理名言：任何看上去很需要脑子的题不会做就想想能不能欧拉回路。

但我觉得更重要的一点或许是：Stay motivated.

• 减少情况：为描述初始状态，考虑加上一个 $(+\infty, 1)$ 的路段。
• 转换条件：注意到 $t_i$ 的限制是 $=$ 但 $s_i$ 的限制是 $\leq$，考虑把 $s_i$ 的限制改成更强的 $=$。遂考虑把原题的变速条件变为减速 $1$ 消耗 $1$ 的代价、加速不消耗代价。
• 建立模型：我们每次变速要么是 $s_i \to t_i$、不消耗代价，要么是 $v + 1 \to v$、代价为 $1$，要么是 $v \to v + 1$、不消耗代价。又因为我们一定会经过所有 $s_i \to t_i$ 的变速过程，这让我们想到欧拉通路。这里我们需要走出一条从 $+\infty$ 出发、经过所有 $s_i \to t_i$ 的欧拉通路，且需要求出代价之和的最小值。
• 简化模型：欧拉通路因为起点和终点的问题往往讨论起来比欧拉回路更为麻烦，又注意到从任何有效的点出发前往 $+\infty$ 都不需要任何代价，于是我们可以直接把前文所述的“欧拉通路”改为“欧拉回路”，答案不变。
• 分析性质：在本题中，由于所有点都在一条链上，则任何一条回路跨过 $v \to v + 1$ 与 $v + 1 \to v$ 的次数恰好相等。首先不难差分出 $s_i \to t_i$ 跨过一段 $v \to v + 1$ 与 $v + 1 \to v$ 的次数之差，不妨设之为 $\text{diff}_v$。若 $\text{diff}_v < 0$，我们显然可以通过若干次无需代价的 $v \to v + 1$ 来抵消；若 $\text{diff}_v > 0$，我们只能通过若干次每次代价为 $1$ 的 $v + 1 \to v$ 来抵消。
• 查漏补缺：注意到上面的分析并没有考虑到现在求出的“欧拉回路”实际上不连通的情况，此时我们需要若干条 $v \to v + 1, v + 1 \to v$ 来使之连通。加上所有的 $v + 1 \to v$ 跑一遍 MST 求出最小代价即可。

就实现而言，对 $s_i, t_i$ 离散化后即可完成上述所有操作。时间复杂度为 $O(n \log n)$。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

typedef struct Edge_tag {
	int start;
	int end;
	int dis;
	Edge_tag(){}
	Edge_tag(int start_, int end_, int dis_){
		start = start_;
		end = end_;
		dis = dis_;
	}
} Edge;

int s[200007], t[200007], a[400007], root[400007], diff[400007];
Edge edge[400007];

bool operator <(const Edge a, const Edge b){
	return a.dis < b.dis;
}

inline void init(int n){
	for (int i = 1; i <= n; i++){
		root[i] = i;
	}
}

int get_root(int x){
	if (root[x] == x) return x;
	return root[x] = get_root(root[x]);
}

inline void merge(int x, int y){
	int x_root = get_root(x), y_root = get_root(y);
	if (x_root != y_root) root[x_root] = y_root;
}

int main(){
	int n, m, k = 0, cnt = 0;
	ll ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> s[i] >> t[i];
	}
	n++;
	s[n] = 0x7fffffff;
	t[n] = 1;
	for (int i = 1; i <= n; i++){
		a[++k] = s[i];
		a[++k] = t[i];
	}
	sort(a + 1, a + k + 1);
	k = unique(a + 1, a + k + 1) - a - 1;
	init(k);
	for (int i = 1; i <= n; i++){
		s[i] = lower_bound(a + 1, a + k + 1, s[i]) - a;
		t[i] = lower_bound(a + 1, a + k + 1, t[i]) - a;
		diff[s[i]]++;
		diff[t[i]]--;
		merge(s[i], t[i]);
	}
	for (int i = 1; i <= k; i++){
		diff[i] += diff[i - 1];
	}
	for (int i = 1; i < k; i++){
		if (diff[i] != 0){
			merge(i, i + 1);
			if (diff[i] > 0) ans += (ll)diff[i] * (a[i + 1] - a[i]);
		}
	}
	for (int i = 1; i < k; i++){
		if (get_root(i) != get_root(i + 1)) edge[++cnt] = Edge(i, i + 1, a[i + 1] - a[i]);
	}
	sort(edge + 1, edge + cnt + 1);
	for (int i = 1; i <= cnt; i++){
		int x_root = get_root(edge[i].start), y_root = get_root(edge[i].end);
		if (x_root != y_root){
			root[x_root] = y_root;
			ans += edge[i].dis;
		}
	}
	cout << ans;
	return 0;
}