你是某著名艺术展览的策展人。你有 $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$ 的数组，其中 $A[i]$ 是画作 $i$ 的尺寸
• $B$：长度为 $N$ 的数组，其中 $B[i]$ 是画作 $i$ 的艺术价值
• $S$：长度为 $M$ 的数组，其中 $S[j]$ 是画框 $j$ 的尺寸
• 该函数应返回可以展出的最大画作数量。

数据范围

• $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 \le 2000$
• 子任务 5（30 分）：无附加限制

样例

输入格式 1

3 3
1 2 3
1 2 4
2 3 5

输出格式 1

3

说明

• 我们有 3 幅画作，尺寸为 $[1, 2, 3]$，艺术价值为 $[1, 2, 4]$。
• 我们有 3 个画框，尺寸为 $[2, 3, 5]$。
• 我们可以选择全部 3 幅画作：画作 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$。

输入格式 2

4 3
1 3 2 4
3 2 3 5
3 6 4

输出格式 2

3

说明

• 我们有 4 幅画作，尺寸为 $[1, 3, 2, 4]$，艺术价值为 $[3, 2, 3, 5]$。
• 我们有 3 个画框，尺寸为 $[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$。

输入格式 3

4 3
1 3 2 4
3 2 3 5
1 1 4

输出格式 3

2

说明

• 我们有 4 幅画作，尺寸为 $[1, 3, 2, 4]$，艺术价值为 $[3, 2, 3, 5]$。
• 我们有 3 个画框，尺寸为 $[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) 并输出返回值。

说明

注意：本题提供的评测程序示例仅用于在本地测试你的解决方案。比赛中实际使用的评测程序可能会有所不同。