记录编号	196026	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.617 s
提交时间	2015-10-20 18:50:11	内存使用	0.61 MiB

#define file
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstring>

using namespace std;
FILE *fin;
template <class te> te qread(te &x) {
	x = 0;
	char c;
	while (! isdigit(c = fgetc(fin)));
	while (isdigit(c)) {
		x = x * 10 + c - '0';
		c = fgetc(fin);
	}
	return x;
}

FILE *fout;
const long long MAXM(1001), MAXN(10001), INF(LLONG_MAX / 3);
long long n,m,k,d[MAXM],f[MAXM],low[MAXN],high[MAXN],x[MAXN],y[MAXN],ans,sum=0;
bool flag;
inline bool live();

main() {
#ifdef file
	fin = fopen("birda.in", "rb");
	fout = fopen("birda.out", "wb");
#else
	fin = stdin;
	fout = stdout;
#endif
	qread(n);
	qread(m);
	qread(k);
	for (long long i = 0; i < n; ++i) {
		qread(x[i]);
		qread(y[i]);
	}
	for (long long i = 0; i <= n; ++i)
		high[i] = m + 1, low[i] = 0;
	for (long long i = 1; i <= k; ++i) {
		long long l, h, p;
		qread(p);
		qread(l);
		qread(h);
		low[p] = l;
		high[p] = h;
	}
	fclose(fin);

	fill(f, f + MAXM, INF);
	ans = INF;

	if (live())
		fprintf(fout, "1\n%lld", ans);
	else
		fprintf(fout, "0\n%lld", sum);
	fclose(fout);
}

inline bool live() {
	fill(f + 1, f + 1 + m, 0);
	for (long long i = 1; i <= n; ++i) {
		flag = false;
		fill(d, d + MAXM, INF);
		for (long long j = 1; j <= m; ++j) {
			if(j-x[i-1]<high[i-1]&&j-x[i-1]>low[i-1]&&d[j]>f[j-x[i-1]]+1)
				d[j] = f[j - x[i - 1]] + 1;
			if (j - x[i - 1] > 0 && d[j] > d[j - x[i - 1]] + 1)
				d[j] = d[j - x[i - 1]] + 1;
		}
		for (long long j = m - x[i - 1] + 1; j <= m; ++j) {
			if (j > low[i - 1] && j < high[i - 1])
				d[m] = min(f[j] + 1, d[m]);
			d[m] = min(d[j] + 1, d[m]);
		}
		for (long long j = 1; j <= m; ++j)
			if(j+y[i-1]>low[i-1]&&j+y[i-1]<high[i-1]&&d[j]>f[j+y[i-1]])
				d[j] = f[j + y[i - 1]];
		for (long long j = low[i] + 1; j < high[i]; ++j)
			if (d[j] < INF)
				flag = true;
		if (! flag)
			return false;
		if (high[i] <= m)
			++sum;
		for (long long i = 0; i <= m; ++i)
			f[i] = d[i];
	}
	for (long long i = 1; i <= m; ++i)
		ans = min(ans, f[i]);
	return true;
}