记录编号	352126	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.808 s
提交时间	2016-11-16 21:28:12	内存使用	39.05 MiB

#include<cstdio>
#include<cstring>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define SUBMIT 2333
int n,m,K;
int x[10010],y[10010];
int F[10010][1010];
int flag[10010],L[10010],R[10010];
const int INF=0x3f3f3f3f;
int ans=0;
inline int GetMax(const int& a,const int& b){
	if(a>b)	return a;
	return b;
}

inline int GetMin(const int& a,const int& b){
	if(a<b)	return a;
	return b;
}


int main(){
	#ifdef SUBMIT
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
	#endif
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x[i],&y[i]);
	}
	int a,b,c;
	for(int i=1;i<=K;++i){
		scanf("%d%d%d",&a,&b,&c);
		flag[a]=true;
		L[a]=b;	R[a]=c;
	}
	memset(F,0x3f,sizeof(F));
	for(int i=1;i<=m;++i){
		F[0][i]=0;
	}
	bool Target;
	for(int i=1;i<=n;++i){
		for(int j=x[i]+1;j<m;++j){
			F[i][j]=GetMin(F[i][j],GetMin(F[i-1][j-x[i]],F[i][j-x[i]])+1);
		}
		for(int k=x[i];k>=0;--k){
			//可能从上一格的顶端平移过来 
			F[i][m]=GetMin(F[i][m],GetMin(F[i-1][m-k],F[i][m-k])+1);
		}
		for(int j=1;j<=m-y[i];++j){
			F[i][j]=GetMin(F[i][j],F[i-1][j+y[i]]);
		}
		if(flag[i]){
			for(int j=1;j<=L[i];++j){
				F[i][j]=INF;
			}
			for(int j=R[i];j<=m;++j){
				F[i][j]=INF;
			}
			Target=false;
			for(int j=L[i]+1;j<R[i];++j){
				if(F[i][j]<INF){
					Target=true;
					break;
				}
			}
			if(!Target){
				printf("%d\n%d",0,ans);
				#ifndef SUBMIT
				getchar();	getchar();
				#endif
				fcl;
			}
			ans++;
		}
	}
	ans=INF;
	for(int i=1;i<=m;++i){
		ans=GetMin(ans,F[n][i]);
	}
	printf("1\n%d",ans);
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}
/*
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3


10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10

*/