#include<iostream>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>

using namespace std;
int n,f[10001][1001]={0},m,a[10001],b[10001],x[10001],y,z,p,ans=1e9,s[10001]={0},q[10001]={0};
//string s;
int main(){
	//freopen("bird.in","r",stdin);
	//freopen("bird.out","w",stdout);
	cin>>n>>m>>p;
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];
	for(int i=1;i<=p;i++){
		cin>>x[i]>>y>>z;
		s[x[i]]=1;
		for(int j=0;j<=m;j++){
			if(j<=y||j>=z)f[x[i]][j]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(f[i][j]!=-1)f[i][j]=1e9;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(f[i][j]!=-1){
				if(j==m){
					if(f[i-1][j]!=-1)f[i][j]=min(f[i][j],f[i-1][j]+1);
					for(int k=1;k<m;k++){
						if(k%a[i-1]==0&&f[i-1][j-k]!=-1)f[i][j]=min(f[i][j],f[i-1][j-k]+k/a[i-1]);
						if(k%a[i-1]!=0&&f[i-1][j-k]!=-1)f[i][j]=min(f[i][j],f[i-1][j-k]+k/a[i-1]+1);
					}
				}
				else{
					if(j+b[i-1]<=m&&f[i-1][j+b[i-1]]!=-1)f[i][j]=min(f[i][j],f[i-1][j+b[i-1]]);
					if(f[i][j-a[i-1]]!=-1&&j>a[i-1])f[i][j]=min(f[i][j],f[i][j-a[i-1]]+1);
					if(f[i-1][j-a[i-1]]!=-1&&j>a[i-1])f[i][j]=min(f[i][j],f[i-1][j-a[i-1]]+1);
				}
			}
		}
	}
	for(int i=1;i<=m;i++)ans=min(f[n][i],ans);
	/*for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<f[i][j]<<" ";
			}
			cout<<endl;
		}*/
	if(ans!=-1&&ans!=1e9)cout<<1<<endl<<ans<<endl;
	if(ans==1e9||ans==-1){
		if(s[0]==1)q[0]=1;
		for(int i=1;i<=n;i++){
			if(s[i]==1)q[i]=q[i-1]+1;
			else q[i]=q[i-1];
		}
		for(int i=0;i<=n;i++){
			int flag=0;
			for(int j=1;j<=m;j++){
				if(f[i][j]>=0&&f[i][j]!=1e9)flag=1;
			}
			if(flag==1)ans=q[i];
			else break;
		}
		cout<<0<<endl<<ans<<endl;
	}
	return 0;
}

代码只有80分

问题出在：比如这组数据：

3 1000 2
2 1
2 1
2 1
1 1 10
2 980 990

输出显示无法到达，但是可以。问题就是每一个f[i][j]是从两个地方转移而来，我们默认f[i][j-a[i-1]]保存了最优值这样就免去过度枚举K了就是第三重循环可是如果没有办法从上面提到的那个地方转移有没有办法从f[i-1][j-a[i-1]]转移的话就出现了问题。比如如果两个地方都是管道。这个问题怎么解决呢？求助谢谢