A - Save the Monsters Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 から N までの番号がついた N 体のモンスターをあなたは飼っています．

あなたのモンスターを討伐するために勇者がやってきました． 勇者はこれから M ターンかけてモンスターに攻撃を仕掛けます． i ターン目には，勇者は以下のいずれかの行動を行います．

  • MP を 1 消費してモンスター X_i を攻撃する． この行動は，モンスター X_i がまだ生きており，かつ勇者の MP が 1 以上のときにのみ行える．

  • 何もしない．

勇者が攻撃を行った場合，あなたはそれに対して以下のいずれかの行動を行います．

  • MP を 1 消費してモンスター X_i を守る． この行動はあなたの MP が 1 以上のときにのみ行える．

  • 何もしない．このとき，モンスター X_i は死んでしまう．

最初のターンが始まる前の段階で，勇者の MP は A，あなたの MP は B です． また，勇者もあなたも 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 ターン目: 勇者がモンスター 1 を攻撃する．
    • あなたは何もせず，モンスター 1 が死ぬ．
  • 2 ターン目: 勇者がモンスター 2 を攻撃する．
    • あなたはモンスター 2 を守る．
  • 3 ターン目: 勇者はなにもしない．

入力例 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

Score : 500 points

Problem Statement

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

Output

Print the answer.

Sample Input 1

2 3 2 1
1 2 1

Sample 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.

Sample Input 2

2 6 3 2
1 1 1 2 2 2

Sample Output 2

1

Sample Input 3

100 1 1 1
100

Sample Output 3

100

Sample 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

Sample Output 4

2