/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
あるコンテストの開催に向けて N 問の問題が提案されました。はじめ、問題 i のスコアは整数 A_i です。
これから、M 人のジャッジが好きな問題に投票します。各ジャッジは、他のジャッジとは独立にちょうど V 問を選び、それらの問題のスコアを 1 ずつ上げます。
M 人のジャッジ全員が投票を行ったあと、N 問の問題がスコアの降順に並べられ、最初の P 問がコンテストの問題セットに採用されます。 同スコアの問題間の順序は、ジャッジ長が任意に決定します。
N 問のうち、問題セットに採用される可能性を持つ問題は何問あるでしょうか？
制約
- 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
入力
入力は以下の形式で標準入力から与えられる。
N M V P A_1 A_2 ... A_N
出力
問題セットに採用される可能性を持つ問題の数を出力せよ。
入力例 1
6 1 2 2 2 1 1 3 0 2
出力例 1
5
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 には採用される可能性はありません。
入力例 2
6 1 5 2 2 1 1 3 0 2
出力例 2
3
採用される可能性があるのは問題 1,4,6 のみです。
入力例 3
10 4 8 5 7 2 3 6 1 6 5 4 6 5
出力例 3
8
Score : 700 points
Problem Statement
N problems are proposed for an upcoming contest. Problem i has an initial integer score of A_i points.
M judges are about to vote for problems they like. Each judge will choose exactly V problems, independently from the other judges, and increase the score of each chosen problem by 1.
After all M judges cast their vote, the problems will be sorted in non-increasing order of score, and the first P problems will be chosen for the problemset. Problems with the same score can be ordered arbitrarily, this order is decided by the chief judge.
How many problems out of the given N have a chance to be chosen for the problemset?
Constraints
- 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
Input
Input is given from Standard Input in the following format:
N M V P A_1 A_2 ... A_N
Output
Print the number of problems that have a chance to be chosen for the problemset.
Sample Input 1
6 1 2 2 2 1 1 3 0 2
Sample Output 1
5
If the only judge votes for problems 2 and 5, the scores will be 2 2 1 3 1 2. The problemset will consist of problem 4 and one of problems 1, 2, or 6.
If the only judge votes for problems 3 and 4, the scores will be 2 1 2 4 0 2. The problemset will consist of problem 4 and one of problems 1, 3, or 6.
Thus, problems 1, 2, 3, 4, and 6 have a chance to be chosen for the problemset. On the contrary, there is no way for problem 5 to be chosen.
Sample Input 2
6 1 5 2 2 1 1 3 0 2
Sample Output 2
3
Only problems 1, 4, and 6 have a chance to be chosen.
Sample Input 3
10 4 8 5 7 2 3 6 1 6 5 4 6 5
Sample Output 3
8