萌新想到一种用二分和st表的乱搞做法，时间上是没问题的，但是WA成75。

大体思路是把线段按左端点排序，利用单调性二分出第一个与左边没有交点的线段，再用st表维护右端点的最小值，判断与左边线段没有交点的线段能否与右边线段有交点，如果可以就转移。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <deque>
#include <queue>
using namespace std;
#define int long long
#define inf 0x7f7f7f7f
#define maxn 3010
int n,dp[maxn],log_2[maxn],f[maxn][21],t[maxn];
struct node{
	int l,r;
	friend bool operator<(node a,node b){
		return a.l<b.l;
	}
}a[maxn];
namespace Main{
	int rd(){
		int x=0,f=1;
		char ch=getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-'){
				f=-1;
			}
			ch=getchar();
		}
		while(ch>='0'&&ch<='9'){
			x=x*10+ch-'0';
			ch=getchar();
		}
		return x*f;
	}
	void wrt(int x){
		int y=10,len=1;
		if(x<0){
			x=-x;
			putchar('-');
		}
		while(y<=x){
			len++;
			y*=10;
		}
		while(len--){
			y/=10;
			putchar(x/y+'0');
			x%=y;
		}
	}
	int _min(int a,int b){
		return a<b? a:b;
	}
	void init(){
		for(int i=1;i<=n;i++){
			f[i][0]=a[i].r;
		}
		for(int j=1;(1<<j)<=n;j++){
			for(int i=1;i<=n-(1<<j)+1;i++){
				f[i][j]=_min(f[i][j-1],f[i+(1<<j-1)][j-1]);
			}
		}
	}
	int query(int l,int r){
		int k=log_2[r-l+1];
		return _min(f[l][k],f[r-(1<<k)+1][k]);
	}
	void MAIN(){
		n=rd();
		for(int i=2;i<=n;i++){
			log_2[i]=log_2[i>>1]+1;
		}
		for(int i=1;i<=n;i++){
			a[i].l=rd();
			a[i].r=rd();
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++){
			t[i]=a[i].l;
		}
		init();
		for(int i=1;i<=n;i++){
			dp[i]=inf;
		}
		a[0].r=-inf;
		for(int i=1;i<=n;i++){
			for(int j=0;j<i;j++){
				if(a[i].l<=a[j].r){
					continue;
				}
				int x=upper_bound(t+1,t+n+1,a[j].r)-t;
				if(x<i){
					if(query(x,i-1)<a[i].l){
						continue;
					}
				}
				dp[i]=_min(dp[i],dp[j]+a[i].r-a[i].l);
			}
		}
		wrt(dp[n]);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	Main::MAIN();
	return 0;
}