← 返回题目列表

AtCoder · wtf22_day1_a

A. 拯救怪物

中文机器翻译题面 查看原题

分数: 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