记录编号	298949	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2016-08-23 14:57:13	内存使用	0.07 MiB

#include<cstdio>
#define inf 0x7fffffff-1
#define min(a,b) ((a)<(b)?(a):(b))
const int N=10005,M=1005;
using namespace std;
int x[N],y[N],up[N],down[N],f[2][M];
inline void in(int &n)
{
	n=0;
	char c;
	while(c>'9'||c<'0') c=getchar();
	do
	  n=n*10+c-'0',c=getchar();
	while(c>='0'&&c<='9');
} 
int cc()
{
    freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
	int i,j,n,m,k,t,count=0,ans=inf;
	in(n),in(m),in(k);
	for(i=0;i<n;i++) in(x[i]),in(y[i]),down[i+1]=0,up[i+1]=m+1;
	for(i=1;i<=k;i++) in(t),in(down[t]),in(up[t]);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		  f[i&1][j]=inf;
		for(j=x[i-1]+1;j<=up[i]-1;j++)
		  f[i&1][j]=min(f[i&1][j],min(f[i&1^1][j-x[i-1]]+1,f[i&1][j-x[i-1]]+1));
	    if(up[i]-1==m)
	      for(j=m-x[i-1];j<=m;j++)
	        f[i&1][m]=min(min(f[i&1][m],f[i&1^1][j]+1),f[i&1][j]+1);
		for(j=down[i]+1;j<=up[i]-1;j++)
		  if(j+y[i-1]<=m) f[i&1][j]=min(f[i&1][j],f[i&1^1][j+y[i-1]]);
	    for(j=1;j<=down[i];j++) f[i&1][j]=inf;
	    for(j=1;j<=m;j++)
	      if(f[i&1][j]!=inf) break;
	    if(j==m+1){printf("0\n%d\n",count);return 0;}
	    if(up[i]!=m+1) count++;
	}
	for(i=1;i<=m;i++)
	  ans=min(ans,f[n&1][i]);
	printf("1\n%d\n",ans);
	return 0;
}
int ccc=cc();
int main(){;}