题目描述

你是一场著名艺术展览的策展人。你有 $N$ 幅画作，每幅画有两个属性：画作尺寸 $A_i$ 和艺术价值 $B_i$。你还有 $M$ 个可用的画框，每个画框有尺寸 $S_j$。

你希望选择并安排 $k$ 幅画作 $i_1, i_2, \dots, i_k$ 以及画框 $j_1, j_2, \dots, j_k$ 进行展示，要求满足：

• 每一幅选中的画作 $i_t$ 放在画框 $j_t$ 中，且画作尺寸不能大于画框尺寸：$A_{i_t} \le S_{j_t}$。
• 选中的画作尺寸按照展示顺序非递减排列：$A_{i_1} \le A_{i_2} \le \dots \le A_{i_k}$。
• 选中的画作艺术价值按照展示顺序非递减排列：$B_{i_1} \le B_{i_2} \le \dots \le B_{i_k}$。

请你求出能够满足上述条件的最大 $k$ 值。

实现细节

你需要实现如下函数：

int32 max_paintings(int32 N, int32 M, int32[] A, int32[] B, int32[] S)

• $N$：画作数量
• $M$：画框数量
• $A$：长度为 $N$ 的数组，第 $i$ 个元素为第 $i$ 幅画作的尺寸
• $B$：长度为 $N$ 的数组，第 $i$ 个元素为第 $i$ 幅画作的艺术价值
• $S$：长度为 $M$ 的数组，第 $j$ 个元素为第 $j$ 个画框的尺寸
• 函数返回能够展示的最大的画作数量

输入格式

第一行：两个整数 $N$ 和 $M$
第二行：$N$ 个整数 $A_1, A_2, \dots, A_N$（画作尺寸）
第三行：$N$ 个整数 $B_1, B_2, \dots, B_N$（艺术价值）
第四行：$M$ 个整数 $S_1, S_2, \dots, S_M$（画框尺寸）

输出格式

输出一个整数，表示能够展示的最大画作数量。

提示

样例

调用 max_paintings(3, 3, [1, 2, 3], [1, 2, 4], [2, 3, 5]) 应返回 3。

• 有三幅画，尺寸为 $[1, 2, 3]$，艺术价值为 $[1, 2, 4]$。
• 有三个画框，尺寸为 $[2, 3, 5]$。
• 可以选全部三幅画：画作1（尺寸1，价值1）放在画框1（尺寸2），画作2（尺寸2，价值2）放在画框2（尺寸3），画作3（尺寸3，价值4）放在画框3（尺寸5）。
• 尺寸递增：$1 \le 2 \le 3$，艺术价值递增：$1 \le 2 \le 4$。

调用 max_paintings(4, 3, [1, 3, 2, 4], [3, 2, 3, 5], [3, 6, 4]) 应返回 3。

• 有四幅画，尺寸为 $[1, 3, 2, 4]$，艺术价值为 $[3, 2, 3, 5]$。
• 有三个画框，尺寸为 $[3, 6, 4]$。
• 可以选择第1、3、4幅画：画作1（尺寸1，价值3）放在画框1（尺寸3），画作3（尺寸2，价值3）放在画框3（尺寸4），画作4（尺寸4，价值5）放在画框2（尺寸6）。
• 尺寸递增：$1 \le 2 \le 4$，艺术价值递增：$3 \le 3 \le 5$。

调用 max_paintings(4, 3, [1, 3, 2, 4], [3, 2, 3, 5], [1, 1, 4]) 应返回 2。

• 有四幅画，尺寸为 $[1, 3, 2, 4]$，艺术价值为 $[3, 2, 3, 5]$。
• 有三个画框，尺寸为 $[1, 1, 4]$。
• 可以选择画作1（尺寸1，价值3）放在画框1或2（尺寸1），再选择画作4（尺寸4，价值5）放在画框3（尺寸4）。
• 尺寸递增：$1 \le 4$，艺术价值递增：$3 \le 5$。

测试器说明

样例测试器按照如下格式读取输入：

• 第1行：两个整数 $N$ 和 $M$
• 第2行：$N$ 个整数 $A_1, A_2, \dots, A_N$（画作尺寸）
• 第3行：$N$ 个整数 $B_1, B_2, \dots, B_N$（艺术价值）
• 第4行：$M$ 个整数 $S_1, S_2, \dots, S_M$（画框尺寸）

测试器会调用 max_paintings(N, M, A, B, S) 并输出返回值。

注意：本问题所附的样例测试器仅用于本地测试，正式测评环境可能与之不同。

数据范围

• $1 \le N, M \le 10^5$
• $1 \le A_i, B_i, S_j \le 10^9$

评分

• 子任务 1（10 分）：$N, M \le 10$
• 子任务 2（20 分）：所有画框尺寸都大于所有画作尺寸（对任意 $i,j$，有 $S_j > A_i$）
• 子任务 3（20 分）：所有艺术价值相等（任意 $i,j$ 有 $B_i = B_j$）
• 子任务 4（20 分）：$N, M < 2000$
• 子任务 5（30 分）：无额外限制

由 ChatGPT 5 翻译