题目描述

あるコンテストの開催に向けて $N$ 問の問題が提案されました。はじめ、問題 $i$ のスコアは整数 $A_i$ です。

これから、$M$ 人のジャッジが好きな問題に投票します。各ジャッジは、他のジャッジとは独立にちょうど $V$ 問を選び、それらの問題のスコアを $1$ ずつ上げます。

$M$ 人のジャッジ全員が投票を行ったあと、$N$ 問の問題がスコアの降順に並べられ、最初の $P$ 問がコンテストの問題セットに採用されます。 同スコアの問題間の順序は、ジャッジ長が任意に決定します。

$N$ 問のうち、問題セットに採用される可能性を持つ問題は何問あるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $V$ $P$ $A_1$ $A_2$ $...$ $A_N$

输出格式

問題セットに採用される可能性を持つ問題の数を出力せよ。

题目大意

有$n$个数$a_1,a_2,\dots,a_n$，需要进行$m$次操作，每次可以选择恰好$v$个数使其加上$1$。

操作完成之后将$a_1,a_2,\dots,a_n$按照不升的顺序排序（相同可以任意摆放），试问如果任意操作，原序列有多少个数有可能最后被排到前$p$位。

$n\le 10^5,\ v,p<n,\ a_i,m\le10^9$。

Translated by Caro23333

6 1 2 2
2 1 1 3 0 2

5

6 1 5 2
2 1 1 3 0 2

3

10 4 8 5
7 2 3 6 1 6 5 4 6 5

8

提示

制約

• $2\ \le\ N\ \le\ 10^5$
• $1\ \le\ M\ \le\ 10^9$
• $1\ \le\ V\ \le\ N\ -\ 1$
• $1\ \le\ P\ \le\ N\ -\ 1$
• $0\ \le\ A_i\ \le\ 10^9$

Sample Explanation 1

$1$ 人しかいないジャッジが問題 $2,5$ に投票した場合、各問のスコアは $2$ $2$ $1$ $3$ $1$ $2$ となり、問題 $4$、そして問題 $1,2,6$ のうちの $1$ 問が採用されます。 ジャッジが問題 $3,4$ に投票した場合、各問のスコアは $2$ $1$ $2$ $4$ $0$ $2$ となり、問題 $4$、そして問題 $1,3,6$ のうちの $1$ 問が採用されます。 よって、問題 $1,2,3,4,6$ には採用される可能性があります。一方で、問題 $5$ には採用される可能性はありません。

Sample Explanation 2

採用される可能性があるのは問題 $1,4,6$ のみです。