#include<bits/stdc++.h> using namespace std; #define ll int #define gc(a) a=getchar() #define pc(a) putchar(a) ll read(){ char c;ll x=0;bool flag=0;gc(c); while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),gc(c);} return flag?-x:x; } void pr(ll x){ if(x<0){x=-x;pc('-');} if(x>9) pr(x/10); pc(x%10+48); } #define inf 0x3f3f3f3f const ll maxn=10005; const ll maxm=10005; struct node { ll id,h,l; bool operator <(const node &a) const { return id<a.id; } }o[maxn]; ll x[maxn],y[maxn],dp[2][maxm],n,m,k,cnt=1,ans; int main() { memset(dp,inf,sizeof(dp)); n=read(),m=read(),k=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(); for(int i=1;i<=k;i++) o[i].id=read(),o[i].l=read(),o[i].h=read(); sort(o+1,o+k+1); for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) dp[i%2][j]=inf; for(int j=x[i]+1;j<=x[i]+m;j++) dp[i%2][j]=min(dp[i%2^1][j-x[i]]+1,dp[i%2][j-x[i]]+1); for(int j=m+1;j<=x[i]+m;j++) dp[i%2][m]=min(dp[i%2][m],dp[i%2][j]); for(int j=1;j<=m-y[i];j++) dp[i%2][j]=min(dp[i%2][j],dp[i%2^1][j+y[i]]); if(i==o[cnt].id) { ans=inf; for(int j=0;j<=o[cnt].l;j++) dp[i%2][j]=inf; for(int j=o[cnt].h;j<=m;j++) dp[i%2][j]=inf; for(int j=1;j<=m;j++) ans=min(dp[i%2][j],ans); if(ans==inf) { pr(0);pc('\n');pr(cnt-1);return 0; } cnt++; } } ans=inf; for(int j=1;j<=m;j++) ans=min(dp[n%2][j],ans); pr(1);pc('\n');pr(ans); return 0; }