现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量减少政府的支出。

第一行包含数据N，M，分别表示区域的个数(0<N≤30000)和房子的数目(0<m≤5000)；

下面的m行描述居民们的号码：B E T，0<B≤E≤30000，T≤E-B+1。

样例输入：

9 4
3 5 2
1 4 2
4 6 2
8 9 2

样例输出：

5
3 4 6 8 9

然后我挂了，每想出来怎么做到区间最优而且……还有要满足最少要种几科

代码（样例都没过）：

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100001;
struct tree{
	int b;
	int e;
	int t;
}a[100001];
int book[MAXN];
bool cmp(const tree &x,const tree &y) {
	return x.e<y.e;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int ans;
	for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].t);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;++i){
		int st=0;
		if(a[i].e-a[i].b==a[i].t-1) {
			ans+=a[i].t;
			for(int j=a[i].e;j>=a[i].b;--j ){
				book[j]=1;
			}
			continue;
		}
		for(int j=a[i].e;j>=a[i].b;--j){
			++st;
			if(st==a[i].t) break;
			if(book[j]==0 ){
				book[j]=1;
				++ans;
			}
			else --st;
		}
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;++i){
		if(book[i])printf("%d ",i);
	}
	return 0;
}