分数: 500 点
问题陈述
你保留 N 怪物编号 1 to N.
一位英雄来杀死你的怪物。 他将采取 M 轮流攻击怪物。 在 i第回合,他执行以下操作之一。
-
消耗 1 攻击怪物的MP X_i。 此动作仅当怪物 X_i 还活着,英雄至少有 1 MP。
-
什么也不做。
如果英雄攻击,您将通过执行以下操作之一进行回应。
-
消耗 1 防御怪物的MP X_i。 仅当您至少拥有以下权限时才能执行此操作 1 MP。
-
什么都不做。怪物会死。
第一回合开始前,英雄已 A MP,你有 B MP。 你和英雄都知道所有的价值观 N, M, A, B,和 X_i。 找到最大的整数 k 满足以下条件。
- 通过使用适当的策略,您至少可以保持 k 无论英雄如何行动,怪物都会活着。
约束
- 1 \leq N,M \leq 250000
- 1 \leq B \leq A \leq M
- 1 \leq X_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A B X_1 X_2 \cdots X_M
输出
打印答案。
示例输入 1
2 3 2 1 1 2 1
示例输出 1
1
你总是可以让至少一只怪物存活。
这是一种可能的进展。
- 第一回合:英雄攻击怪物 1.
- 你什么都不做,怪物 1 去世。
- 第二回合:英雄攻击怪物 2.
- 你保卫怪物 2.
- 第三回合:英雄什么都不做。
示例输入 2
2 6 3 2 1 1 1 2 2 2
示例输出 2
1
示例输入 3
100 1 1 1 100
示例输出 3
100
示例输入 4
6 20 16 5 5 6 1 3 2 1 4 3 2 4 1 4 4 6 3 3 5 2 2 2
示例输出 4
2