Problem Description

You have $ N $ monsters numbered from $ 1 $ to $ N $.

A hero has come to defeat your monsters. The hero will attack the monsters over $ M $ turns. On the $ i $-th turn, the hero will perform one of the following actions:

• Consume $ 1 $ MP to attack monster $ X_i $. This action can only be performed if monster $ X_i $ is still alive and the hero has at least $ 1 $ MP.
• Do nothing.

If the hero attacks, you can respond with one of the following actions:

• Consume $ 1 $ MP to protect monster $ X_i $. This action can only be performed if you have at least $ 1 $ MP.
• Do nothing. In this case, monster $ X_i $ will die.

Before the first turn starts, the hero has $ A $ MP and you have $ B $ MP. Both the hero and you know the values of $ N, M, A, B, X_i $. Your task is to find the maximum integer $ k $ that satisfies the following condition:

• By taking appropriate strategies, you can ensure that at least $ k $ monsters survive until the end, regardless of the hero's actions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A $ $ B $ $ X_1 $ $ X_2 $ $\cdots$ $ X_M $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 3 2 1
1 2 1

Sample Output #1

1

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

Notes/Hints

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.

Sample Explanation 1

You can always ensure that at least $ 1 $ monster survives. Here is an example of a possible scenario:
- Turn 1: The hero attacks monster $ 1 $.
- You do nothing, and monster $ 1 $ dies.
- Turn 2: The hero attacks monster $ 2 $.
- You protect monster $ 2 $.
- Turn 3: The hero does nothing.

见题面 Input 部分

见题面 Output 部分