

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