记录编号	38156	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 滑雪训练	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.200 s
提交时间	2012-04-14 09:50:28	内存使用	42.34 MiB

/*
ID:alertya1
PROG:ski
LANG:C++
*/
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("ski.in");
ofstream fout("ski.out");
int T,S,N,Max_T,road[20005],Max;bool flag[13005][105],Record[20005];
class Le
{
public:
	int St,last,lev,Data;
}Lesson[202],f[13005][205];
void Initialize()
{
int i,St_init,En_init;
	fin>>T>>S>>N;
	for(i=1;i<=S;i++)
	{
		fin>>Lesson[i].St>>Lesson[i].last>>Lesson[i].lev;
		Max_T=max(Max_T,Lesson[i].lev);
		Record[Lesson[i].St]=true;
	}
	for(i=1;i<=N;i++)
	{
		fin>>En_init>>St_init;
		Max_T=max(Max_T,En_init);
		if(road[En_init]==0 || road[En_init]>St_init)
			road[En_init]=St_init;
	}
	for(i=1;i<=Max_T;i++)
		if(road[i-1]!=0)
			if(road[i]!=0)
				road[i]=min(road[i],road[i-1]);
			else
				road[i]=road[i-1];
}

void dp()
{
int i,j,k;
	flag[0][1]=true;
	for(i=0;i<=T;i++)
	{
		for(j=1;j<=Max_T;j++)
			if(flag[i][j])
			{
				flag[i+1][j]=true;f[i+1][j].Data=max(f[i][j].Data,f[i+1][j].Data);
				if(road[j])
				{
					flag[i+road[j]][j]=true;
					f[i+road[j]][j].Data=max(f[i+road[j]][j].Data,f[i][j].Data+1);
				}
				if(Record[i])
					for(k=1;k<=S;k++)
						if(Lesson[k].St==i)
						{
							f[i+Lesson[k].last][Lesson[k].lev].Data=max(f[i+Lesson[k].last][Lesson[k].lev].Data,f[i][j].Data);
							flag[i+Lesson[k].last][Lesson[k].lev]=true;
						}
		Max=max(f[i][j].Data,Max);
			}
	}
	fout<<Max<<endl;
}

int main()
{
	Initialize();
	
	dp();
	
	fin.close();
	fout.close();
	return 0;
}