题目：http://codeforces.com/problemset/problem/1132/C

题意：就是雇佣q-2个画家完成最多的工作；

思路：如果题目要求改成雇佣q-1个画家你会做的话，那么q-2也就可以完成；

           我们枚举不要每一个画家时，从剩下的q-1个画家中删除一个画家的影响所能得到的最大值即可。

刚开始一直想不清楚怎样把两个画家的影响分开算，看了题解后才明白菜是原罪。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5 * 1000 + 10;
int n, L[maxn], R[maxn],q;

int solve(int id) {
	int num[maxn]; memset(num,0,sizeof(num));		//num[]记录的是每一个画家画的部分前缀
	for (int i = 1; i <= q; i++)if(i!=id)num[L[i]]++, num[R[i] + 1]--;   //当i==id不记录在内即可消除第i个画家的影响
	
	int one[maxn], ans = 0; memset(one,0,sizeof(one));    //One记录的是只由一个画家完成的地方
	for (int i = 1; i <= n; i++) {
		num[i] += num[i - 1];
		if (num[i])ans++; 
		one[i] = num[i] == 1;
	}

	int sum[maxn], c = 0; memset(sum,0,sizeof(sum));     //记录one的前缀和
	for (int i = 1; i <= n; i++)c += one[i], sum[i] += c;

	int res= n+10;
	for (int i = 1; i <= q; i++)if (i != id)res = min(sum[R[i]]-sum[L[i]-1],res);  //sum[R[i]]-sum[L[i]-1]：第i个画家单独完成的数量

	return ans - res;
}

int main() {

	cin >> n>>q;
	
	for (int i = 1; i <= q; i++) {
		scanf("%d%d",L+i,R+i);
	}

	int ans = 0;
	for (int i = 1; i <= q; i++) {   //枚举每一个画家
		ans = max(ans,solve(i));
	}
	
	cout << ans << endl;

	return 0;
}