记录编号	192214	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.375 s
提交时间	2015-10-10 06:19:47	内存使用	10.03 MiB

#include<cstdio>
#include<cstring>
#include<vector>

#define inf 1000000000
#define MAXN 10010
#define MAXM 1010
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

void read(int & x)
{
	x=0;
	char c=getchar();
	while(c<'!')	c=getchar();
	while(c>'!')	x=x*10+c-'0',c=getchar();
}

int n,m,g,f[2][MAXM],x[MAXN],y[MAXN];
bool flag[MAXN][MAXM],fla[MAXN];

int main()
{
	
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
	//memset(f,0x3f,sizeof(f));
	read(n);read(m);read(g);
	for(int i=1;i<=n;i++)
		read(x[i]),read(y[i]);
	for(int i=1;i<=g;i++){
		int a,x,y;
		read(a);read(x);read(y);
		fla[a]=1;
		for(int j=1;j<=x;j++)
			flag[a][j]=1;
		for(int j=y;j<=m;j++)
			flag[a][j]=1;
	}
	for(int i=1;i<=m;i++)
		f[0][i]=0;
	int now=1,last=0,ans=0;
	for(int i=1;i<=n;i++,now^=1,last^=1){
		for(int j=1;j<m;j++){
			f[now][j]=inf;
			if(j-x[i]>0){
				f[now][j]=MIN(f[now][j],f[last][j-x[i]]+1);
				f[now][j]=MIN(f[now][j],f[now][j-x[i]]+1);
			}	
		}
		f[now][m]=inf;
		for(int j=1;j<=m;j++){
			if(j+y[i]<=m)	f[now][j]=MIN(f[now][j],f[last][j+y[i]]);
			int k;
			if(j==m)	k=1;	
			else		k=(m-j-1)/x[i]+1;
			f[now][m]=MIN(f[now][m],f[last][j]+k);
		}
		for(int j=1;j<=m;j++){
			if(flag[i][j]==1)	f[now][j]=inf;
			else {
				if(f[now][j]<inf-10000)	ans=i;
				//printf("%d %d %d %d\n",i,j,f[now][j],ans);
			}
		}
	}
	if(ans==n){
		ans=0x3fffffff;
		for(int i=1;i<=m;i++)
			ans=MIN(ans,f[last][i]);
		printf("1\n%d",ans);
	}else{
		int t=0;
		for(int i=1;i<=ans;i++){
			if(fla[i])
				t++;
		}
		printf("0\n%d",t);
	}
	getchar();getchar();
	return 0;
}