#P11789. [JOI 2019 Final] 画展 / Exhibition
[JOI 2019 Final] 画展 / Exhibition
题目描述
你将举办一个画展。在展览中,你需要将一些画放入一些画框中并摆放成一排。
展览有 幅候选画,编号从 到 。画 具有大小 和美观度 。
另外,有 个候选画框,编号从 到 。画框 的大小为 。
只有大小不超过 的画才能放入画框 中。每个画框中最多只能放一幅画。每幅要展出的画都必须放在一个画框中。
考虑到美观因素,展出的画必须满足以下条件:
- 对于任意两幅相邻的画,右边的画框大小不小于左边的画框。
- 对于任意两幅相邻的画,右边的画的美观度不小于左边的画的美观度。
你需要求出你最多能展出多少幅画。
输入格式
一行两个整数 。
接下来 行,每行两个整数 ,含义如题所示。
接下来 行,每行一个整数 ,含义如题所示。
输出格式
一行一个整数,表示能展示的画的数量。
3 4
10 20
5 1
3 5
4
6
10
4
2
3 2
1 2
1 2
1 2
1
1
2
4 2
28 1
8 8
6 10
16 9
4
3
0
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
3
提示
【数据范围与约定】
- 。
- 。
- 。
- 。
- 对于 的数据,,。
- 对于 的数据,,。
- 对于 的数据,无特殊限制。