// Problem: P1941 [NOIP2014 提高组] 飞扬的小鸟
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1941
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, k, x[10005], y[10005], cnt;
struct Pipe {
  int p, l, h;
} p[10005];
bool cmp(Pipe a, Pipe b) { return a.p < b.p; }
long long f[2][1005], ans;
int main() {
  cnt = 1;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
  for (int i = 1; i <= k; i++) cin >> p[i].p >> p[i].l >> p[i].h;
  sort(p + 1, p + k + 1, cmp);
  memset(f, 0x3f, sizeof(f));
  for (int i = 0; i <= m; i++) f[0][i] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) f[i % 2][j] = 0x3f3f3f3f3f3f3f3fll;
    for (int j = x[i] + 1; j <= x[i] + m; j++)
      f[i % 2][j] = min(f[i % 2][j - x[i]], f[i % 2 ^ 1][j - x[i]]) + 1;
    for (int j = m + 1; j <= x[i] + m; j++)
      f[i % 2][m] = min(f[i % 2][m], f[i % 2][j]);
    for (int j = 1; j <= m - y[i]; j++)
      f[i % 2][j] = min(f[i % 2][j], f[i % 2 ^ 1][j + y[i]]);
    if (i == p[cnt].p) {
      ans = 0x3f3f3f3f3f3f3f3fll;
      for (int j = 1; j <= p[cnt].l; j++) f[i % 2][j] = 0x3f3f3f3f3f3f3f3fll;
      for (int j = p[cnt].h; j <= m; j++) f[i % 2][j] = 0x3f3f3f3f3f3f3f3fll;
      for (int j = 1; j <= m; j++) ans = min(ans, f[i % 2][j]);
      if (ans == 0x3f3f3f3f3f3f3f3fll) {
        cout << "0\n" << cnt - 1;
        return 0;
      }
      cnt++;
    }
  }
  ans = 0x3f3f3f3f3f3f3f3fll;
  for (int j = 1; j <= m; j++) ans = min(ans, f[n % 2][j]);
  cout << "1\n" << ans;
  return 0;
}

记录

#10输入

#10输出