记录编号	454907	评测结果	AAAAAAAAAAAAAATTATAT
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	80
用户昵称	Fisher.	是否通过	未通过
代码语言	C++	运行时间	5.074 s
提交时间	2017-09-30 11:07:18	内存使用	77.61 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#include <cstring>
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=10010;
const int maxm=1010;
const int inf=0x3f3f3f3f;
int n,m,k;
int sheng[maxn],jiang[maxn];
struct guan{
	int xia,shang;
}g[maxn];
int f[maxn][maxm][2];
int ans=0x7fffffff;
bool you[maxn];
inline void bu(){
	int tot=0;
	for(int i=0;i<=n;i++){
		if(!you[i])continue;
		int ok=0;
		for(int j=g[i].xia+1;j<=g[i].shang-1;j++){
			if(f[i][j][1]!=inf||f[i][j][0]!=inf)ok=1;
		}
		if(ok==1)tot++;
		else{
			printf("%d\n",tot);
			return ;
		}
	}
}
int main(){
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
	n=read();m=read();k=read();
	for(int i=0;i<n;i++){
		sheng[i]=read();jiang[i]=read();
	}
	for(int i=1;i<=k;i++){
		int x=read();you[x]=1;
		g[x].xia=read();g[x].shang=read();
	}
	memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=m;i++)f[0][i][0]=f[0][i][1]=0;
	int guo=0;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			int gf=0;
			if((you[i])&&(j<=g[i].xia||j>=g[i].shang)){continue;}
			if(f[i][j][0]==inf&&f[i][j][1]==inf){continue;}
			int sjie=min(m,j+sheng[i]);
			int xjie=j-jiang[i];
			int sok=0,xok=0;
			int ok=0;
			int cnt=0;
			for(;;){
				cnt++;
				if(ok==1)break;
				if(sjie==m)ok=1;
				sok=0;
				if(!you[i+1]||(sjie>g[i+1].xia&&sjie<g[i+1].shang))sok=1;
				if(sok){
					if(f[i][j][0]!=inf)
						f[i+1][sjie][1]=min(f[i+1][sjie][1],f[i][j][0]+cnt);
					if(f[i][j][1]!=inf)
						f[i+1][sjie][1]=min(f[i+1][sjie][1],f[i][j][1]+cnt);
				}
				sjie=min(m,sjie+sheng[i]);
			}
			if((!you[i+1]||(xjie>g[i+1].xia&&xjie<g[i+1].shang))&&xjie>0)xok=1;
			if(xok){
				if(f[i][j][0]!=inf)
					f[i+1][xjie][0]=min(f[i+1][xjie][0],f[i][j][0]);
				if(f[i][j][1]!=inf)
					f[i+1][xjie][0]=min(f[i+1][xjie][0],f[i][j][1]);
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(f[n][i][0]!=inf)ans=min(ans,f[n][i][0]);
		if(f[n][i][1]!=inf)ans=min(ans,f[n][i][1]);
	}
	if(ans!=0x7fffffff){
		puts("1");
		printf("%d\n",ans);
	}
	else{
		puts("0");
		bu();
	}
	return 0;
}