#P11789. [JOI 2019 Final] 画展 / Exhibition

[JOI 2019 Final] 画展 / Exhibition

题目描述

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

展览有 NN 幅候选画,编号从 11NN。画 ii 具有大小 SiS_i 和美观度 ViV_i

另外,有 MM 个候选画框,编号从 11MM。画框 jj 的大小为 CjC_j

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

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

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

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

输入格式

一行两个整数 N,MN,M

接下来 NN 行,每行两个整数 Si,ViS_i,V_i,含义如题所示。

接下来 MM 行,每行一个整数 CiC_i,含义如题所示。

输出格式

一行一个整数,表示能展示的画的数量。

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

提示

【数据范围与约定】

  • 1N100000 1\le N \le 100000
  • 1M100000 1 \le M \le 100000
  • 1Si109 1\le S_i \le 10^9
  • 1Vi,Cj109 1\le V_i,C_j \le 10^9
  1. 对于 10% 10 \% 的数据,N10 N \le 10 M10 M \le 10
  2. 对于 40% 40 \% 的数据,N1000 N \le 1000 M1000 M \le 1000
  3. 对于 50% 50 \% 的数据,无特殊限制。