AT_joi2019ho_b 展覧会 (Exhibition)

你打算举办一场画展。在展览会上，你需要将若干幅画装入画框，并从左到右依次排列展示。 有 $N$ 幅备选画作，编号为 $1$ 到 $N$。第 $i$ 幅画的尺寸为 $S_i$，价值为 $V_i$。 另外，有 $M$ 个画框，编号为 $1$ 到 $M$。第 $j$ 个画框的尺寸为 $C_j$。只有尺寸不超过 $C_j$ 的画作才能放入第 $j$ 个画框。每个画框最多只能放入一幅画。 所有展出的画作都必须装在某个画框中。为了美观，展出的画作必须满足以下条件： - 对于任意相邻的两幅画，右侧画作所用画框的尺寸不小于左侧画作所用画框的尺寸。 - 对于任意相邻的两幅画，右侧画作的价值不小于左侧画作的价值。 你希望展出的画作数量尽可能多。 给定所有备选画作的数量、画框数量及它们的尺寸和价值，请编写程序求出最多能展出多少幅画作。

输入按以下格式从标准输入读入。 > $N$ $M$ > $S_1$ $V_1$ > $\vdots$ > $S_N$ $V_N$ > $C_1$ > $\vdots$ > $C_M$

请输出展览会上最多能展出的画作数量。

### 限制条件 - $1 \leq N \leq 100\,000$。 - $1 \leq M \leq 100\,000$。 - $1 \leq S_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 - $1 \leq V_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 - $1 \leq C_j \leq 1\,000\,000\,000$（$1 \leq j \leq M$）。 ### 子任务 1. ($10$ 分) $N \leq 10$，$M \leq 10$。 2. ($40$ 分) $N \leq 1\,000$，$M \leq 1\,000$。 3. ($50$ 分) 无额外限制。 # 样例解释 1 在本输入输出样例中，可以依次排列（画作 $2$，画框 $2$）、（画作 $1$，画框 $3$），这样可以展出 $2$ 幅画作。无法展出 $3$ 幅或更多画作，因此输出 $2$。这里，（画作 $i$，画框 $j$）表示画作 $i$ 被装入画框 $j$。 # 样例解释 2 - - - - - - # 样例解释 3 - - - - - - 由 ChatGPT 4.1 翻译