RE #7 #8 #9 #10 #11 #13

WA #3 #6 #12

#include<bits/stdc++.h>
using namespace std;
#define Maxn 10005
#define Maxm 1005
#define Inf 0x3f3f3f3f
int n,m,k,x[Maxn],y[Maxn],dp[Maxm][Maxn];
pair<int,int> cube[Maxn];
#define up(a) cube[a].first
#define down(a) cube[a].second
void minf(int &a,int b) {
	a=min(a,b);
}

int main() {
	memset(dp,0x3f,sizeof dp);
	cin>>n>>m>>k;
	for(int i=0; i<n; i++) {
		cin>>x[i]>>y[i];
		dp[0][i+1]=0;
		up(i+1)=down(i+1)=-1;
	}
	int h;
	for(int i=0; i<k; i++) {
		cin>>h;
		cin>>down(h)>>up(h);
		for(int j=0; j<=down(h); j++) {
			dp[h][j]=-Inf;
		}
		for(int j=up(h); j<=m; j++) {
			dp[h][j]=-Inf;
		}
	}
	for(int i=0; i<n; i++) {
		for(int j=1; j<=m; j++) {
			if(dp[i][j]==-Inf) continue;
	//		printf("Now is(%d,%d) Can Up %d;Down %d|Go %d\n",i,j,x[i],y[i],(m-j)/x[i]);
			if(x[i]!=0) {
				for(int k=0; k<=(m-j)/x[i]; k++) {
					if(k==0)
					{
					if(j-y[i]>0)
					{
					minf(dp[i+1][j-y[i]],dp[i][j]);		
					}
					}
					else
					{
					if(j+k*x[i]>m) minf(dp[i+1][m],dp[i][j]+k);
					else minf(dp[i+1][j+k*x[i]],dp[i][j]+k);	
					}
				}
				if((m-j)/x[i]==0)
				{
					minf(dp[i+1][m],dp[i][j]+1);
					if(j-y[i]>0) minf(dp[i+1][j-y[i]],dp[i][j]);
				}
			} else {
				minf(dp[i+1][j],dp[i][j]+1);
				if(j-y[i]>0) minf(dp[i+1][j-y[i]],dp[i][j]);
			}
//			test(i,j);
		}
	}
//	test(0,0);
	int mres=Inf;
	for(int i=1; i<=m; i++) {
		if(dp[n][i]!=Inf) minf(mres,dp[n][i]);
	}
	if(mres!=Inf) cout<<1<<endl<<mres;
	else {
		int res=0;
		for(int i=1; i<n; i++) {
			bool f=false;
			for(int j=1; j<=m; j++) {
				if(dp[i][j]!=-Inf&&dp[i][j]!=Inf) {
					f=true;
					break;
				}
			}
			if(f&&up(i)!=-1&&down(i)!=-1) {
				res++;
			}
		}
		cout<<0<<endl<<res;
	}
	return 0;
}