AT_joi2019ho_b.展覧会 (Exhibition)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你打算举办一场画展。在展览会上，你需要将若干幅画装入画框，并从左到右依次排列展示。

有 $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
```
3 4
10 20
5 1
3 5
4
6
10
4
```
输出#1
```
2
```
输入#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

说明/提示

限制条件

$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$ ）。

子任务

( $10$ 分) $N \leq 10$ ， $M \leq 10$ 。
( $40$ 分) $N \leq 1\,000$ ， $M \leq 1\,000$ 。
( $50$ 分) 无额外限制。

样例解释 1

在本输入输出样例中，可以依次排列（画作 $2$ ，画框 $2$ ）、（画作 $1$ ，画框 $3$ ），这样可以展出 $2$ 幅画作。无法展出 $3$ 幅或更多画作，因此输出 $2$ 。这里，（画作 $i$ ，画框 $j$ ）表示画作 $i$ 被装入画框 $j$ 。

样例解释 2

样例解释 3

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页