防晒 Sunscreen

题目描述

有 C 头奶牛准备在海滩晒太阳。为避免晒伤，又能达到日光浴的效果，第 i 头奶牛只能使用 SPF 值位于闭区间 [minSPF_i,maxSPF_i] 内的防晒霜。SPF 太低会晒伤，太高则不能晒黑。

有 L 瓶防晒霜，第 j 瓶的 SPF 值为 SPF_j，最多能供 cover_j 头奶牛使用。每头奶牛只能使用一瓶中的防晒霜，不能混用。求最多能满足多少头奶牛。

输入格式

第一行两个整数 C、L。 接下来 C 行，每行两个整数 minSPF_i、maxSPF_i。 接下来 L 行，每行两个整数 SPF_j、cover_j。

输出格式

一个整数，表示最多可以满足的奶牛数量。

数据范围

1 ≤ C,L ≤ 2500，1 ≤ minSPF_i ≤ maxSPF_i ≤ 1000，1 ≤ SPF_j ≤ 1000。 cover_j 是该瓶可供使用的奶牛数，原始题面未给出其数值上限。

来源

POJ 3614 Sunscreen，《算法竞赛进阶指南》0x07 贪心。

样例 1

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

2