传送门
上升看成完全背包。
下降看成01背包。
注意边界转移就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e4+5,M=1e3+5;
int n,m,k,f[N][M<<1],ban[N][2],X[N],Y[N];
bool is[N];
inline void calc(int pos){
int ret=0;
for(int i=1;i<pos;++i)if(is[i])++ret;
printf("0\n%d",ret);
exit(0);
}
int main(){
memset(f,0x3f,sizeof(f)),n=read(),m=read(),k=read();
for(int i=1;i<=m;++i)f[0][i]=0;
for(int i=1;i<=n;++i)X[i]=read(),Y[i]=read(),ban[i][0]=0,ban[i][1]=m+1;
for(int i=1,p,d,u;i<=k;++i)p=read(),is[p]=1,ban[p][0]=read(),ban[p][1]=read();
for(int i=1;i<=n;++i){
for(int j=X[i]+1;j<=m+X[i];++j)f[i][j]=min(f[i][j],min(f[i-1][j-X[i]]+1,f[i][j-X[i]]+1));
for(int j=m+1;j<=m+X[i];++j)f[i][m]=min(f[i][m],f[i][j]);
for(int j=1;j<=m-Y[i];++j)f[i][j]=min(f[i][j],f[i-1][j+Y[i]]);
for(int j=1;j<=ban[i][0];++j)f[i][j]=f[0][0];
for(int j=ban[i][1];j<=m;++j)f[i][j]=f[0][0];
bool ff=0;
for(int j=ban[i][0]+1;j<=ban[i][1]-1;++j)if(f[i][j]^f[0][0]){ff=1;break;}
if(!ff)calc(i);
}
int ans=f[0][0];
for(int i=1;i<=m;++i)ans=min(ans,f[n][i]);
printf("1\n%d",ans);
return 0;
}