3622 - 发工资(wage)

题目描述

南国因为停电,全国的印钞机都无法工作,于是这个月南国国王决定用金砖替代钞票来给大臣发工资。

每块金砖都有一定的价值,对于每个大臣,国王要保证他们领到的金砖价值至少不低于他们的工资,否则就会得不到那个大臣的信任,但是也不能给得太多,如果金砖的价值超过了那个大臣的工资太多,国王宁愿不要他的信任!当然,如果不想得到某个大臣的信任,就没有必要给他发工资了。

对于每个大臣,国王对给他们的金砖价值的上限要求也可能不同,且每个大臣至多只能发到一块金砖。

现在给你国库中的所有金砖和所有大臣的消息,国王想知道他最多能得到多少大臣的信任。

输入

从文件 wage.in 中读入数据。

第一行是两个整数 n 和 m ,表示大臣的数量和金砖的数量。

接下来 n 行,每行两个正整数ai,bi,第 i+1 行表示第 i 个大臣的工资和可以获得金砖的价值上限。

接下来 m 行,每行一个正整数ci,表示国库中其中一块金砖的价值。

输出

输出到文件 wage.out 中。

输出一个整数,表示在限制条件下,国王最多能得到多少个大臣的信任。

样例

输入

4 6
3 16
9 18
12 19
7 13
14
6
18
3
11
6

输出

4

输入

4 7
19 19
5 19
17 19
19 20
17
14
1
11
5
20
3

输出

3

输入

7 5
16 18
15 18
7 12
17 17
16 17
4 16
12 12
14
17
15
12
6

输出

4
说明

【样例 1 解释】

第一位大臣发价值为 3 的金砖,第二位大臣发价值为 14 的金砖,第三位大臣发价值为 18 的金砖,第四位大臣发价值为 11 的金砖。

对于 100% 的数据:1 ≤ ai ,bi,ci ≤ 1000

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 62
通过人数 13
金币数量 2 枚
难度 基础


上一题 下一题