这应该不是背包吧。。。

思路：每一个位置都可能由上一列的位置转移而来，具体就是 $dp_{i,j}=\max \{dp_{i-1,j+down_i-1}, \max \{dp_{i-1,j-up_{i-1} \times s,j-up_{i-1} \times s>0}\}\}$

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e4 + 5;
const int M = 1e3 + 5;

struct col
{
	int l, h;
}
c[N];

int n, m, k, p, l, h;
int up[N], down[N], dp[N][M];

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	int i, j, s;
	for (i = 0; i < n; i++)
		scanf("%d %d", &up[i], &down[i]),
		c[i].h = m + 1, c[i].l = 0;
	c[n].h = m + 1, c[n].l = 0;
	for (i = 1; i <= k; i++)
	{
		scanf("%d %d %d", &p, &l, &h);
		c[p].l = l, c[p].h = h;
	}
	std::memset(dp, 0x3F, sizeof dp);
	for (i = 1; i <= m; i++)
		dp[0][i] = 0;
	for (i = 1; i <= n; i++)
		for (j = c[i].l + 1; j < c[i].h; j++)
		{
			if (j + down[i - 1] <= m)
				dp[i][j] = std::min(dp[i][j], dp[i - 1][j + down[i - 1]]);
			for (s = 1; j - s * up[i - 1] > 0; s++)
				dp[i][j] = std::min(dp[i][j], dp[i - 1][j - s * up[i - 1]] + s);
			if (j == m)
				for (s = 1; s < up[i - 1] && j - s > 0; s++)
					dp[i][j] = std::min(dp[i][j], dp[i - 1][j - s] + 1);
		}
	int ans(0x3F3F3F3F);
	for (i = 1; i <= m; i++)
		ans = std::min(ans, dp[n][i]);
	if (ans < 0x3F3F3F3F)
	{
		printf("1\n%d\n", ans);
		return 0;
	}
	ans = 0;
	bool flag;
	for (i = 1; i <= n; i++)
	{
		flag = false;
		for (j = 1; j <= m; j++)
			if (dp[i][j] < 0x3F3F3F3F)
			{
				flag = true;
				break;
			}
		if (!flag)
			break;
		if (c[i].h != m + 1)
			ans++;
	}
	printf("0\n%d", ans);
	return 0;
}
/*
  3 9  
  9 9  
  1 2  
  1 3  
  1 2  
  1 1  
  2 1  
  2 1  
  1 6  
  2 2 
 */