NOIP2014 飞扬的小鸟

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct ios{
	//The template of Mingrui Sheng 
    inline char gc(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char ch,sgn;ch=gc(),sgn=0;
        for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch==‘-‘;}
        for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^‘0‘);
        sgn&&(x=-x); return *this;
    }
    //Orz 浮尘ii* 
}io;
int n,m,k,ans=1<<30,x[10005],y[10005],l[10005],r[10005],f[10005][2005],xx,yy,zz;
bool ok[10005];
int main(){
	memset (f,0x3f3f3f3f,sizeof (f));
	io>>n>>m>>k;//scanf ("%d%d%d",&n,&m,&k);
	for (register int i=1;i<=n;++i){
	    io>>x[i]>>y[i];
	    l[i]=1;r[i]=m;
	}
	for (register int i=1;i<=k;++i){
		io>>xx>>yy>>zz;
		ok[xx]=1;
		l[xx]=yy+1;r[xx]=zz-1;
	}
	for (register int i=1;i<=m;++i) f[0][i]=0;
	for (register int i=1;i<=n;++i){
		for (register int j=x[i]+1;j<=x[i]+m;++j) f[i][j]=min(f[i-1][j-x[i]],f[i][j-x[i]])+1;
		for (register int j=m+1;j<=m+x[i];++j) f[i][m]=min(f[i][m],f[i][j]);
		for (register int j=1;j<=m-y[i];++j) f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
		for (register int j=1;j<l[i];++j) f[i][j]=0x3f3f3f3f;
		for (register int j=r[i]+1;j<=m;++j) f[i][j]=0x3f3f3f3f;
	}
	for (register int i=1;i<=m;++i){
		if (f[n][i]<ans) ans=f[n][i];
	}
	if (ans<0x3f3f3f3f){
		printf ("1\n%d\n",ans);
		return 0;
	}
	ans=0;
	for (register int i=n;i>=1;--i){
		for (register int j=1;j<=m;++j){
			if (f[i][j]<0x3f3f3f3f){
				for (register int k=1;k<=i;++k) if (ok[k]) ++ans;
				printf ("0\n%d\n",ans);
				return 0;
			}
		}
	}
	return 0;
}