#3011. 「JOI 2019 Final」画展

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

译自 JOI 2019 Final T2「展覧会 / Exhibition

你将举办一个画展。在展览中,你需要将一些画放入一些画框中并摆放成一排。

展览有 N 幅候选画,编号从 1 N 。画 i ( 1 \le i \le N) 具有大小 S_i 和美观度 V_i

另外,有 M 个候选画框,编号从 1 M 。画框 j ( 1 \le j \le M) 的大小为 C_j

只有大小不超过 C_j 的画才能放入画框 j 中。每个画框中最多只能放一幅画。每幅要展出的画都必须放在一个画框中。

考虑到美观因素,展出的画必须满足以下条件:

  • 对于任意两幅相邻的画,右边的画框大小不小于左边的画框
  • 对于任意两幅相邻的画,右边的画的美观度不小于左边的画的美观度

你需要求出你最多能展出多少幅画。

输入格式

从标准输入中读取数据。

第一行两个整数 N M

接下来 N 行,第 i 行为两个整数 S_i V_i

接下来 M 行,第 i 行为一个整数 C_i

输出格式

输出数据到标准输出中。

输出一行一个整数,表示你最多能展出的画的数量。

样例

样例输入 1
3 4
10 20
5 1
3 5
4
6
10
4
样例输出 1
2
样例说明 1

在这个样例中,一个合法的方案是:从左往右,第二幅画放在第二个框中,第一幅画放在第三个框中。

样例输入 2
3 2
1 2
1 2
1 2
1
1
样例输出 2
2
样例输入 3
4 2
28 1
8 8
6 10
16 9
4
3
样例输出 3
0
样例输入 4
8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543
样例输出 4
3

数据范围与提示

Subtask # 分值 N, M
1 10 N, M \le 10
2 40 N, M \le 1000
3 50 N, M \le 10^5

对于所有输入数据,有 1 \le N, M \le 10^5, 1 \le S_i, V_i, C_j \le 10^9 (1 \le i \le N, 1 \le j \le M)