#P3614. Sunscreen

Sunscreen

题目描述

为了避免晒黑时出现难看的灼伤,每头奶牛(共 CC 头,1C25001 ≤ C ≤ 2500)在海滩上时都必须涂抹防晒霜。奶牛 ii 对防晒霜的 SPFSPF 值有最小和最大要求(1minSPFi1000minSPFimaxSPFi10001 ≤ minSPFi ≤ 1000;minSPFi ≤ maxSPFi ≤ 1000):如果 SPF 值过低,奶牛会被晒伤;如果过高,奶牛则完全晒不黑。

奶牛们有一个野餐篮,里面装着 L 瓶防晒霜(1L25001 ≤ L ≤ 2500)。第 ii 瓶防晒霜的 SPFSPF 值为 SPFi1SPFi1000SPFi(1 ≤ SPFi ≤ 1000),最多可给 coveri 头奶牛使用。每头奶牛只能使用一瓶防晒霜。

在给定的防晒霜条件下,最多有多少头奶牛能成功防晒?

输入格式

第 1 行:两个空格分隔的整数 CCL L 第 2 到 C+1C+1 行:每行两个整数 minSPFiminSPFimaxSPFi maxSPFi,表示奶牛 iiSPFSPF 值的要求 第 C+2C+2C+L+1C+L+1 行:每行两个整数 SPFiSPFicovericoveri,表示第 ii 瓶防晒霜的 SPFSPF 值和可覆盖奶牛数 输出格式 一个整数,表示最多能防晒的奶牛数量

输入样例 1

3 2

3 10

2 5

1 5

6 2

4 1

输出样例 1

2