AT_wtf22_day1_a.Save the Monsters

你拥有 $N$ 只编号从 $1$ 到 $N$ 的怪兽。

有一位勇者前来讨伐你的怪兽。勇者将在接下来的 $M$ 个回合中对怪兽发起攻击。在第 $i$ 回合，勇者可以选择以下两种行动之一：

• 消耗 $1$ 点 MP 攻击怪兽 $X_i$。只有当怪兽 $X_i$ 还存活且勇者的 MP 不小于 $1$ 时，才能进行此操作。
• 什么都不做。

如果勇者进行了攻击，你可以对该攻击做出以下两种应对：

• 消耗 $1$ 点 MP 保护怪兽 $X_i$。只有当你的 MP 不小于 $1$ 时，才能进行此操作。
• 什么都不做。在这种情况下，怪兽 $X_i$ 会死亡。

在第一个回合开始前，勇者拥有 $A$ 点 MP，你拥有 $B$ 点 MP。此外，勇者和你都完全知晓 $N, M, A, B, X_i$ 的所有数值。请你求出满足以下条件的最大整数 $k$：

• 无论勇者采取何种行动策略，只要你采取最优策略，最终都能保证至少有 $k$ 只怪兽存活。

输入通过标准输入按以下格式给出：

$N$ $M$ $A$ $B$ $X_1$ $X_2$ $\cdots$ $X_M$

请输出答案。

限制条件

• $1 \leq N, M \leq 250000$
• $1 \leq B \leq A \leq M$
• $1 \leq X_i \leq N$
• 所有输入均为整数。

样例解释 1

你一定可以保证至少有 $1$ 只怪兽存活。以下是可能的流程示例：

• 第 $1$ 回合：勇者攻击怪兽 $1$。
• 你什么都不做，怪兽 $1$ 死亡。
• 第 $2$ 回合：勇者攻击怪兽 $2$。
• 你保护怪兽 $2$。
• 第 $3$ 回合：勇者什么都不做。

由 ChatGPT 4.1 翻译