Save the Monsters

AtCoder

IDwtf22_day1_a

Time2000ms

Memory256MB

Difficulty—

You keep $N$ monsters numbered $1$ to $N$. A hero has come to slay your monsters. He will take $M$ turns to attack the monsters. In the $i$\-th turn, he performs one of the following actions. * Consume $1$ MP to attack monster $X_i$. This action can only be performed when monster $X_i$ is still alive and the hero has at least $1$ MP. * Do nothing. If the hero attacks, you will respond by performing one of the following actions. * Consume $1$ MP to defend monster $X_i$. This action can only be performed when you have at least $1$ MP. * Do nothing. The monster will die. Before the first turn begins, the hero has $A$ MP, and you have $B$ MP. Both you and the hero know all values of $N$, $M$, $A$, $B$, and $X_i$. Find the greatest integer $k$ that satisfies the following condition. * By using an appropriate strategy, you can keep at least $k$ monsters alive no matter how the hero acts. ## Constraints * $1 \leq N,M \leq 250000$ * $1 \leq B \leq A \leq M$ * $1 \leq X_i \leq N$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $A$ $B$ $X_1$ $X_2$ $\cdots$ $X_M$ [samples]

Samples

Input #1

2 3 2 1
1 2 1

Output #1

1

You can always keep at least one monster alive.
Here is one possible progression.

*   The first turn: The hero attacks monster $1$.
    *   You do nothing, and monster $1$ dies.
*   The second turn: The hero attacks monster $2$.
    *   You defend monster $2$.
*   The third turn: The hero does nothing.

Input #2

2 6 3 2
1 1 1 2 2 2

Output #2

Input #3

100 1 1 1
100

Output #3

Input #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

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Save the Monsters",
    "description": {
      "content": "You keep $N$ monsters numbered $1$ to $N$. A hero has come to slay your monsters. He will take $M$ turns to attack the monsters. In the $i$\\-th turn, he performs one of the following actions. *   Con",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "wtf22_day1_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You keep $N$ monsters numbered $1$ to $N$.\nA hero has come to slay your monsters. He will take $M$ turns to attack the monsters. In the $i$\\-th turn, he performs one of the following actions.\n\n*   Con...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments