[Usaco2007 Nov]tanning分配防晒霜

奶牛们计划去海滩上享受日光浴。为了避免皮肤被阳光灼伤，所有 $C$ 头奶牛都必须在出门前涂抹防晒霜，其中 $1\le C\le 2500$ 。

第 $i$ 头奶牛适合的防晒霜 SPF 值范围为 $[\mathrm{minSPF}_i,\mathrm{maxSPF}_i]$ ，其中 $1\le \mathrm{minSPF}_i\le 1000$ ，且 $\mathrm{minSPF}_i\le \mathrm{maxSPF}_i\le 1000$ 。如果涂抹的防晒霜 SPF 值过小，阳光仍会灼伤奶牛的皮肤；如果 SPF 值过大，则会使日光浴与待在屋里睡觉几乎没有区别。

奶牛们准备了 $L$ 瓶防晒霜，其中 $1\le L\le 2500$ 。第 $i$ 瓶防晒霜的 SPF 值为 $\mathrm{SPF}_i$ ，满足 $1\le \mathrm{SPF}_i\le 1000$ ，且该瓶防晒霜可以供 $\mathrm{cover}_i$ 头奶牛使用。每头奶牛只能使用某一瓶防晒霜，不能混合使用多瓶防晒霜。

请计算最多有多少头奶牛能够在不被阳光灼伤的前提下享受日光浴。

时间限制： $5\times 10^3\ \mathrm{ms}$ 。
内存限制： $2^{16}\ \mathrm{KB}$ 。

输入格式

第 $1$ 行包含两个用空格隔开的整数 $C$ 和 $L$ 。
第 $2$ 至第 $C+1$ 行，每行包含两个用空格隔开的整数 $\mathrm{minSPF}_i$ 和 $\mathrm{maxSPF}_i$ ，表示第 $i$ 头奶牛适合的 SPF 值范围。
第 $C+2$ 至第 $C+L+1$ 行，每行包含两个用空格隔开的整数 $\mathrm{SPF}_i$ 和 $\mathrm{cover}_i$ ，表示第 $i$ 瓶防晒霜的 SPF 值及其可供使用的奶牛数量。

输出格式

输出一个整数，表示最多有多少头奶牛能够享受到日光浴。

样例输入

3 2
3 10
2 5
1 5
6 2
4 1

输入说明:

    一共有3头奶牛，2瓶防晒霜。3头奶牛适应的SPF值分别为3..10，2..5，以
及1..5。2瓶防晒霜的SPF值分别为6（可使用2次）和4（可使用1次）。可能的分
配方案为：奶牛1使用第1瓶防晒霜，奶牛2或奶牛3使用第2瓶防晒霜。显然，最
多只有2头奶牛的需求能被满足。

样例输出

样例解释

一种可行的分配方案是：第 $1$ 头奶牛使用第 $1$ 瓶防晒霜，第 $2$ 头或第 $3$ 头奶牛使用第 $2$ 瓶防晒霜。因此最多有 $2$ 头奶牛能够满足需求。

数据范围

$1\le C\le 2500$ ；
$1\le L\le 2500$ ；
$1\le \mathrm{minSPF}_i\le 1000$ ；
$\mathrm{minSPF}_i\le \mathrm{maxSPF}_i\le 1000$ ；
$1\le \mathrm{SPF}_i\le 1000$ 。

来源与许可

本题为 USACO 2007 年 $11$ 月试题「tanning」，题面与测试数据整理自 BZOJ 1707。

样例 1

输入

3 2
3 10
2 5
1 5
6 2
4 1

输入说明:

    一共有3头奶牛，2瓶防晒霜。3头奶牛适应的SPF值分别为3..10，2..5，以
及1..5。2瓶防晒霜的SPF值分别为6（可使用2次）和4（可使用1次）。可能的分
配方案为：奶牛1使用第1瓶防晒霜，奶牛2或奶牛3使用第2瓶防晒霜。显然，最
多只有2头奶牛的需求能被满足。