记录编号	139951	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.237 s
提交时间	2014-11-17 20:23:15	内存使用	36.88 MiB

/*========================================================*/
/*======================BY ASM.DEF========================*/
/*========================================================*/
#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout 
#else
FILE *in = fopen("birda.in", "r");
FILE *out = fopen("birda.out", "w");
#endif
#define pb push_back
#define iter(v) v::iterator
template<typename T> inline bool getd(T &x){
	int c = fgetc(in);
	bool minus = 0;
	while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
	if(c == EOF)return 0;
	if(c == '-'){
		minus = 1;
		x = 0;
	}
	else x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
	if(minus)x = -x;
	return 1;
}
using namespace std;
/*==========================================================*/
const int maxn = 10000 + 5, maxm = 1000 + 5, INF = 0x3f3f3f3f;
int cnt[maxn][maxm] = {0};
int n, m, k, X[maxn], Y[maxn], H[maxn], L[maxn] = {0};

inline void init(){
	getd(n), getd(m), getd(k);
	int i;
	H[0] = m + 1;
	for(i = 0;i < n;++i){
		getd(X[i]), getd(Y[i]);
		H[i+1] = m + 1;//“撞到”？
	}
	while(k--){
		getd(i);
		getd(L[i]), getd(H[i]);
	}
	cnt[0][0] = INF;
}

inline void work(){
	int i, j, done = 0, Min;
	bool ok;
	for(i = 1;i <= n;++i){
		ok = 0;
		for(j = 0;j <= m;++j)
			cnt[i][j] = INF;
		for(j = 1;j < H[i];++j){
			Min = INF;
			if(j - X[i-1] > L[i-1]){
				if(cnt[i-1][j-X[i-1]] + 1 < Min)
					Min = cnt[i-1][j-X[i-1]] + 1;
				if(cnt[i][j-X[i-1]] + 1 < Min)
					Min = cnt[i][j-X[i-1]] + 1;
			}
			if(Min < INF)cnt[i][j] = Min, ok = 1;
		}
		for(j = L[i] + 1;j < H[i];++j)
			if(j + Y[i-1] < H[i-1] && cnt[i-1][j+Y[i-1]] < cnt[i][j])
				cnt[i][j] = cnt[i-1][j+Y[i-1]], ok = 1;
		for(j = 0;j <= L[i];++j)
			cnt[i][j] = INF;
		if(H[i] == m + 1){//无障碍
			for(j = H[i]-X[i-1];j < H[i];++j){
				if(cnt[i-1][j] + 1 < cnt[i][m])
					cnt[i][m] = cnt[i-1][j] + 1;
				if(cnt[i][j] + 1 < cnt[i][m])
					cnt[i][m] = cnt[i][j] + 1;
			}
			if(cnt[i][m] < INF)ok = 1;
		}
		if(!ok){
			fprintf(out, "0\n%d\n", done);
			return;
		}
		if(H[i] != m + 1)
			++done;
	}
	Min = INF;
	for(j = L[n]+1;j < H[n];++j)
		if(cnt[n][j] < Min)Min = cnt[n][j];
	fprintf(out, "1\n%d\n", Min);
}

int main(){
	
	init();
	
	work();
	
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
	#endif
	return 0;
}