← 返回题目列表

AtCoder · joi2019ho_b

B. 展览

中文机器翻译题面 查看原题

配点: 100 点

您正计划举办画展。展览中,几幅画将被放置在画框内,从左到右排成一排展示。

展览候选作品 N 可用, 它们的编号最大为1 到 N 。图片 i (1 \leqq i \leqq N) 的大小是 S_i,值为 V_i 。

此外,这些图片还有相框。 它们的编号最大为 M 可用, 它们的编号最大为1 到 M 。相框 j (1 \leqq j \leqq M) 的大小是 C_j 。相框 j 的大小为 C_j 只能包含以下图片。1 相框可能会花费很多。 1 只能插入一张图片。

所有展示的画作都必须装在某种画框中。为了具有良好的外观,展出的画作必须满足以下条件:

  • 左右相邻哪一个 对于 2 图片,包含右侧图片的帧的大小大于或等于包含左侧图片的帧的大小。 对于
  • 左右相邻哪一个 对于 2 图片,右边图片的值大于左边图片的值。

您想展示尽可能多的画作。

给定候选画作的数量、相框的数量以及它们的大小和价值,编写一个程序来计算要展出的最大画作数量。


入力

输入是按以下格式从标准输入给出的。

N M
S_1 V_1
\vdots
S_N V_N
C_1
\vdots
C_M

出力

展览中展出的画作的最大数量按标准输出输出。 1 行。 在


制約

  • 1 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq 100\,000.
  • 1 \leqq S_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq V_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq C_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq M).

小課題

  1. (10 点) N \leqq 10,M \leqq 10.
  2. (40 点) N \leqq 1\,000,M \leqq 1\,000.
  3. (50 点)没有额外的限制。

入力例 1

3 4
10 20
5 1
3 5
4
6
10
4

出力例 1

2

在此输入/输出示例中,从左到右(图片 通过排列 2, 額縁 2),(絵 1, 額縁 3), 您可以显示2 张图片。3 张图片,因此 输出2 。这里,(图 i, 額縁 j) 是一个相框 j 中的图片 代表 i 。


入力例 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