{"raw_statement":[{"iden":"problem statement","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*   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.\n    \n*   Do nothing.\n    \n\nIf the hero attacks, you will respond by performing one of the following actions.\n\n*   Consume $1$ MP to defend monster $X_i$. This action can only be performed when you have at least $1$ MP.\n    \n*   Do nothing. The monster will die.\n    \n\nBefore 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.\n\n*   By using an appropriate strategy, you can keep at least $k$ monsters alive no matter how the hero acts."},{"iden":"constraints","content":"*   $1 \\leq N,M \\leq 250000$\n*   $1 \\leq B \\leq A \\leq M$\n*   $1 \\leq X_i \\leq N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $A$ $B$\n$X_1$ $X_2$ $\\cdots$ $X_M$"},{"iden":"sample input 1","content":"2 3 2 1\n1 2 1"},{"iden":"sample output 1","content":"1\n\nYou can always keep at least one monster alive.\nHere is one possible progression.\n\n*   The first turn: The hero attacks monster $1$.\n    *   You do nothing, and monster $1$ dies.\n*   The second turn: The hero attacks monster $2$.\n    *   You defend monster $2$.\n*   The third turn: The hero does nothing."},{"iden":"sample input 2","content":"2 6 3 2\n1 1 1 2 2 2"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"100 1 1 1\n100"},{"iden":"sample output 3","content":"100"},{"iden":"sample input 4","content":"6 20 16 5\n5 6 1 3 2 1 4 3 2 4 1 4 4 6 3 3 5 2 2 2"},{"iden":"sample output 4","content":"2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}