配点: 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).
小課題
- (10 点) N \leqq 10,M \leqq 10.
- (40 点) N \leqq 1\,000,M \leqq 1\,000.
- (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