10 10 6

3 9

9 9

1 2

1 3

1 2

1 1

2 1

2 1

1 6

2 2

1 2 7

5 1 5

6 3 5

7 5 8

8 7 9

9 1 3

1

6

10 10 4

1 2

3 1

2 2

1 8

1 8

3 2

2 1

2 1

2 2

1   2

1 0 2

6 7 9

9 1 4

3 8 10  

0

3

#include<iostream>

#include<cstdio>

using namespace std;

#define maxn 10010

int n,m,cdt,ans=0x7fffffff,ans1;

bool flag,th[maxn];

struct node{

    int x,y;

}p[maxn];

struct Node{

    int l,h;

}c[maxn];

void dfs(int now,int hi,int cnt,int step){

    if(cnt>ans)return;

    if(now==n){

        ans=min(ans,cnt);

        flag=;

        return;

    }

    ans1=max(ans1,step);

    if(hi-p[now].y<c[now+].h&&hi-p[now].y>c[now+].l){//说明可以不点击

        if(th[now+]){//下一秒要到达的地方有管道

            dfs(now+,hi-p[now].y,cnt,step+);

        }

        else dfs(now+,hi-p[now].y,cnt,step);

    }

    int sum=;

    while(){

        hi+=p[now].x;sum++;

        if(hi>m)hi=m;

        if(hi>=c[now+].h)break;

        if(hi<=c[now+].l)continue;

        if(th[now+]){

            dfs(now+,hi,cnt+sum,step+);

        }

        else {

            dfs(now+,hi,cnt+sum,step);

        }

        if(hi==m)return;

    }

}

int main(){

    //freopen("Cola.txt","r",stdin);

    scanf("%d%d%d",&n,&m,&cdt);

    for(int i=;i<=n;i++)c[i].l=,c[i].h=m+;

    for(int i=;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);

    int u,v,w;

    for(int i=;i<=cdt;i++){

        scanf("%d%d%d",&u,&v,&w);

        c[u].l=v;c[u].h=w;

        th[u]=;

    }

    for(int i=;i<=m;i++)dfs(,i,,);

    if(flag){//能到达终点

        printf("1\n");

        printf("%d",ans);

    }

    else {

        printf("0\n");

        printf("%d",ans1);

    }

}

/*

    50分做法：暴力dfs

    70分做法：

    向上的是完全背包，向下的是01背包

    令f[i][j]表示到达横坐标为i，高度为j的最小点击数

    向上的状态转移方程：f[i][j]=min( f[i-1][j-up[i-1]*k]+k )   k<=m/up[i-1]

    向下的状态转移方程：f[i][j]=min( f[i-1][j+down[i-1]])

    时间复杂度：O（nm2）

    100分做法：

    在向上的状态转移方程中，

    若p=j-up[i-1]*k， 那么到达状态p 和 到达状态j 的 很多起点是重复的

    也就是说，由重复的相同状态转移到了不同状态

    优化这个重复的相同状态

    假设一次上升高度x

        f[i][j-x]= min（ f[i-1][ (j-x)-x*(k-1) ]+k-1 ）

        原式:f[i][j]=min（ f[i-1][j-x*k]+k）

    发现 当k>1时，f[i][j]=f[i][j-x]+1

    所以新的向上的状态转移方程：f[i][j]=min（f[i-1][j-x],f[i][j-x]）+1

*/

#include<cstdio>

#include<algorithm>

#define N 10001

#define inf 20001

using namespace std;

int n,m,k,ok;

int up[N],down[N],top[N],bot[N];

int f[N][];

bool have[N];

int main() {

    scanf("%d%d%d",&n,&m,&k);

    int x;

    for(int i=; i<n; i++) scanf("%d%d",&up[i],&down[i]);

    for(int i=; i<=k; i++) {

        scanf("%d",&x);

        have[x]=true;

        scanf("%d%d",&bot[x],&top[x]);

    }

    for(int i=; i<=n; i++)

        if(!top[i]) top[i]=m+;

    for(int i=; i<=n; i++)

        for(int j=; j<=m; j++)

            f[i][j]=inf;

    //for(int i=0; i<=m; i++) f[0][i]=0;

    for(int i=; i<=bot[]; i++) f[][i]=inf;

    for(int i=top[]; i<=m; i++) f[][i]=inf;

    for(int i=; i<=n; i++) {

        for(int j=up[i-]+; j<=m; j++) f[i][j]=min(f[i-][j-up[i-]],f[i][j-up[i-]])+;

        for(int j=m-up[i-]; j<=m; j++) f[i][m]=min(f[i][m],min(f[i][j],f[i-][j])+);

        for(int j=; j<=m-down[i-]; j++) f[i][j]=min(f[i][j],f[i-][j+down[i-]]);

        for(int j=; j<=bot[i]; j++) f[i][j]=inf;

        for(int j=top[i]; j<=m; j++) f[i][j]=inf;

        if(!have[i]) continue;

        int j;

        for(j=bot[i]+; j<=top[i]; j++)

            if(f[i][j]<inf) {

                ok++;

                break;

            }

        if(j>top[i]) {

            printf("0\n%d",ok);

            return ;

        }

    }

    int sum=inf;

    for(int i=; i<=m; i++) sum=min(sum,f[n][i]);

    printf("1\n%d",sum);

}