stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

long long n, m, v, p, a[100001];

bool cmp(long long x, long long y)

{

    return x > y;

}

int main(int argc, char const *argv[])

{

    scanf("%lld%lld%lld%lld", &n, &m, &v, &p);

    for (int i = 1; i <= n; i++)

    {

        scanf("%lld", &a[i]);

    }

    sort(a + 1, a + n + 1, cmp);

    long long ans = p, sum = 0;

    for (int i = p + 1; i <= n; i++)

    {

        if (a[i] + m < a[p])

        {

            break;

        }

        if (v - n + i <= p)

        {

            ans++;

        }

        else

        {

            if (((v - p - n + i) * m - sum - 1) / (i - p) + 1 + a[p] <= a[i] + m)

            {

                ans++;

            }

        }

        sum += a[p] - a[i];

    }

    printf("%lld\n", ans);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.127362185355155x):
#include <cstdio>

#include <algorithm>

#define ll long long

using namespace std;

const int N=1e5+5;

int n,m,v,p;

ll a[N],sum[N];

bool check(int x){

	if(a[x]+m<a[p]) return 0;

	return 1ll*m*v<=1ll*(p-1ll)*m+1ll*(n-x+1)*m-1ll*(sum[x-1]-sum[p-1])+1ll*(a[x]+m)*(x-p);

}

signed main() {

	scanf("%d%d%d%d",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+n+1);

	reverse(a+1,a+n+1);

	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

	int l=p,r=n,ans=p;

	while(l<=r){

		int mid=l+r>>1;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	printf("%d\n",ans);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

const int N=1e5+10;



int n,m,v,p;

int a[N];



bool check(int mid){

	ll ans=0;

	if(a[mid]+m<a[p]) return false;

	for(int i=1;i<=n;i++){

		if(i>=p&&i<mid) ans+=(ll)(a[mid]+m-a[i]);

		else ans+=(ll)m;

	}

//	cout<<' '<<ans<<endl; 

	if((ll)m*(ll)v>ans) return false;

	return true;

}



bool cmp(int a,int b){

	return a>b;

}



int main(){

	cin.tie(0);

	cin>>n>>m>>v>>p;

	for(int i=1;i<=n;i++) cin>>a[i];

	sort(a+1,a+n+1,cmp);

	int l=1,r=n;

	while(l<r){

		int mid=(l+r+1)>>1;

		if(mid<=p) l=mid;

		else if(check(mid)) l=mid;

		else r=mid-1;

//		cout<<l<<' '<<r<<' ';

//		cout<<check(mid)<<endl;

	}

	cout<<l<<endl;

	return 0;

}

/*

	while(r>=l){

        mid=(r+l)>>1;

       // cout << "*******" << '\n';

        ll z=check(mid);

        if(z<m)

        r=mid-1;

        else{

            l=mid+1;

        }

    }

*/

// Faster C++ solution for the same problem (measured speedup: 5.198059479424043x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;

using ll = long long;

int n, m, v, p;

const int maxn = 1e5+7;

vector<ll>a;

ll pre[maxn];

int main()

{

	ios::sync_with_stdio(false);cin.tie(0);

	cin >> n >> m >> v >> p;

	a.resize(n);

	for(auto &u:a){

		cin >> u;

	}

	sort(a.begin(), a.end(), [&](int a, int b){

		return a > b;

	});

	for(int i=0; i<n; ++i){

		pre[i+1] = pre[i]+a[i];

	}

	ll ans = p;

	for(int i=p; i<n; ++i){

		if(a[i]+m<a[p-1])break;

		ll cur = v-(n-(i-p+1));//需要超过的人里的投票数 

		if(cur<=0){//全给不会产生影响的人投票 

			ans++;

			continue;

		}

		if(cur*m<=(i-p+1)*(a[i]+m)-(pre[i]-pre[p-1]))ans++;//需要超过的人里投票 

	}

	cout << ans; 

} 

// Faster C++ solution for the same problem (measured speedup: 5.270300446324245x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;



int n, m, v, w;

vector<int> a, p;



bool chk(int x){

        if (x + w >= n) return true;

        int r = v - w - x;

        if (r < 0) {

            for (int i = x + 1; i + w <= n; ++i)

                if (a[p[x]] + m < a[p[i]]) return false;

            return true;

        }

        else {

            ll s = 1ll * r * m;

            for (int i = x + 1; i + w <= n; ++i) {

                int y = a[p[x]] + m - a[p[i]];

                if (y > 0)

                    s -= a[p[x]] + m - a[p[i]];

                else if (y < 0)

                    return false;

            }

            return s <= 0;

        }

    }



int main(void) {

    scanf("%d%d%d%d", &n, &m, &v, &w);

    a.resize(n, 0);

    p.resize(n, 0);

    for (int& i : a) scanf("%d", &i);

    iota(p.begin(), p.end(), 0);

    sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });



    int l = 0, r = n - 1;

    while (l <= r) {

        int mid = (l + r) >> 1;

        if (chk(mid)) r = mid - 1;

        else l = mid + 1;

    }





    printf("%d\n", n - l);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.181315432635559x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<stdio.h>

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<string>

#include<stack>

#include<set>

#include<map>

#include<time.h>

#include<cstdlib>

typedef long long ll;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define mm(a) memset(a,0,sizeof(a))

#define lr rt<<1

#define rr rt<<1|1

#define sync std::ios::sync_with_stdio(false);std::cin.tie(0);

#define inf 0x3f3f3f3f

#define eqs 1e-8

#define lb(x) (x&(-x))

#define ch(a) (int(a-'a')+1)

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef pair<int,int> pii;

const double pi=acos(-1);

const int maxn=100005;

const ll Mod=1000000007;





ll a[maxn];

bool cmp(ll a,ll b)

{

    return a>b;

}



int main()

{

    sync;

    ll n,m,v,p;

    cin>>n>>m>>v>>p;

    for(int i=1;i<=n;i++)

    {

        cin>>a[i];

    }

    sort(a+1,a+n+1,cmp);

    ll d=a[p];

    int sum=0;

    ll s=0;

    ll c=0;

    for(int i=p;i<=n;i++)

    {

        if(a[i]>d)

        {

            sum++;

            continue;

        }

        if(d-m>a[i])

            break;

        if(s<=1ll*(n-v)*m+1ll*a[i]*c)

        {

            sum++;

            s+=a[i];

            c++;

        }

        else

            break;

    }

    cout<<sum+p-1<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.2508170047751825x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define m_k make_pair

#define int long long

using namespace std;

const int N=1e5+100;

int n,m,v,p,a[N],sum[N],ans;

signed main()

{

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+1+n);

	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

	a[n+1]=inf;

	for (int i=n;i>=1;i--)

	{

		if (i>=v)

		{

			int pos=upper_bound(a+1,a+2+n,a[i]+m)-a;

			if (n-pos+1<p) ans++;

		}

		else

		{

			int pos=upper_bound(a+1,a+2+n,a[i]+m)-a;

			if (n-pos+1>=p) continue;

			if (v-i-p+1<=0)

			{

				ans++;

				continue;

			}

			int cnt=v-i-p+1;

			int l=i+1,r=min(n-p+1,pos-1);

			if (r-l+1>=cnt && cnt*m<=(a[i]+m)*(r-l+1)-(sum[r]-sum[l-1])) ans++;

		}

	}

	printf("%lld\n",ans);

}


// Faster C++ solution for the same problem (measured speedup: 5.1294940625066765x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,v,p,s,mx,c,r,b,a[100005];

signed main()

{

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",a+i);

	sort(a+1,a+n+1),c=a[n-p+1],b=0,r=p,v=n-v,s=0,mx=0;

	for(int i=n;i>=1;i--) if(a[i]<c) break;else b++;

	for(int i=n-p;i>=1;i--)

	{

		s+=(a[i+1]-a[i])*(n-p+1-i);

		if(s<=min(n-p,v)*m&&a[n-p+1]-a[i]<=m) r++;else break;

	}

	return printf("%lld\n",r),0;

}


// Faster C++ solution for the same problem (measured speedup: 5.126518358612301x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#define ri register

#define inf 0x7fffffff

#define E (1)

#define mk make_pair

#define int long long

using namespace std; const int N=200010;

inline int read()

{

	int s=0, w=1; ri char ch=getchar();

	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar(); return s*w;

}

int n,m,v,p,a[N],now,res;

inline bool cp(int x,int y) { return x>y; }

signed main()

{

	n=read(), m=read(), v=read(), p=read();

	for(ri int i=1;i<=n;i++) a[i]=read();

	sort(a+1,a+1+n,cp); now=p;

	for(ri int i=p+1;i<=n;res+=a[p]-a[i], i++)

	{

		if(a[p]>a[i]+m) break; // m 次全部加上去还不如别人不加

		if(p-1+n-i+1>=v || ((v-(p-1+n-i+1))*m-res-1)/(i-p)<=a[i]-a[p]-1+m) now++;// 否则把数都加给 i 和后面以及 p-1 和前面

		// 还有一种情况，还得给 p 到 i-1 这里放，那么尽量使得放了之后平均最小即可。 

	} printf("%lld\n",now);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.109913916117584x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<time.h>

using namespace std;

typedef long long ll;

int n,m,v,p,a[100005],b[100005],ans,pth_min;

bool judge(int pth){

	ll res=0;

	int i;

	for(i=1;i<=n;i++)

		b[i]=min(m,pth-a[i]);

	sort(b+1,b+n+1);

	if(b[p]<0)

		return 0;

	for(i=1;i<=n;i++)

		res+=i<=p-1?m:b[i];

	return res>=(ll)m*v;

}

int solve(){

	int l=0,r=2e9,mid,res=-1;

	while(l<=r){

		mid=((ll)l+r)>>1;

		if(judge(mid))

			r=mid-1,res=mid;

		else

			l=mid+1;

	}

	return res;

}

int main(){

	scanf("%d%d%d%d",&n,&m,&v,&p);

	int i;

	for(i=1;i<=n;i++)

		scanf("%d",&a[i]);

	pth_min=solve();

	for(i=1;i<=n;i++)

		ans+=a[i]+m>=pth_min;

	printf("%d\n",ans);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.141941965786126x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int N=200005;

#define int long long

int n,m,v,p,pos,tmp;

int a[N],sum[N],t[N];



bool cmp(int x,int y)

{

	return x>y;

}



bool check(int x)

{

	//cout<<a[x]<<" "<<k<<" "<<tt<<endl;

	if(x<=p) return 1;

	int rest=v-(p-1)-(n-x+1);

	if(rest<0) rest=0;

	int choose=n-(p-1)-(n-x+1);

	int Sum=0;

	for(int i=1;i<=choose;i++) t[i]=a[i+p-1]-a[x],Sum+=t[i];

	//cout<<rest<<endl; for(int i=1;i<=choose;i++) cout<<t[i]<<" "; cout<<endl; cout<<endl;

	if(a[x]+m<a[p]) return 0;

	return Sum<=m*(choose-rest);

}



signed main() 

{

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+n+1,cmp);

	int now=1;

	for(int i=1;i<=n;i++)

	{

		sum[i]=sum[i-1]+a[i];

	}

	int l=p,r=n,mid,best;

	while(l<=r)

	{

		mid=(l+r)>>1;

		if(check(mid)) l=mid+1,best=mid;

		else r=mid-1;

	}

	cout<<best<<endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.148027434367806x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#define int long long



using namespace std;

const int N = 1e5 + 5;



int n, m, v, p;

int a[N], t[N];



bool judge(int x) {

	if (x <= p) return 1;

	if (a[x] + m < a[p]) return 0;

	if (v <= p - 1 && a[x] + m >= a[p]) return 1;

	for (register int i = 1; i <= n; i++)

		t[i] = a[i];

	for (register int i = 1; i < p; i++)

		t[i] += m;

	

	int cost = m * (p - 1);

	for (register int i = n, c = v - p; i > x && c; c--)

		cost += m, t[--i] += m;

	cost += m;

	

	int left = m * v - cost;

	for (register int i = p; i < x; i++) {

		int inc = min(m, max(a[x] + m - a[i], 0ll));

		inc = min(inc, left);

		left -= inc, t[i] += inc;

	}

	

	return a[x] + m >= t[p] && left <= 0;

}



signed main() {

	cin >> n >> m >> v >> p;

	for (register int i = 1; i <= n; i++)

		cin >> a[i];

	

	sort(a + 1, a + 1 + n, greater<int>());

	

	int l = 1, r = n, ret = 0;

	while (l <= r) {

		int mid = (l + r) >> 1;

		if (judge(mid)) ret = mid, l = mid + 1;

		else r = mid - 1;

	}

	

	cout << ret << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.191394004656485x):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5+10;

int a[maxn];

int cmp(const int a,const int b){

    return a>b;

}

int n,m,v,p;

int b[maxn];

bool judge(int mid){

    //printf("hello %lld\n",mid);

    if(mid<=p)return true;

    if(a[mid]+m<a[p])return false;

    if(v<=p-1&&a[mid]+m>=a[p])return true;

    for(int i=1;i<=n;i++)b[i]=a[i];

    int temp=0;

    int inx=n,cnt=v-p+1;

    for (int i=n,j=v-p;i>mid&&j;i--,j--){

        temp+=m;

        b[i]+=m;

    }

    temp+=m*p;

    int now=a[mid]+m;

    int res=m*v-temp;

    int ww=a[p];

    for(int i=p;i<mid;i++){

        int add=min(m,max(now-a[i],0ll));

        if(add>res)add=res;

        res-=add;

        b[i]+=add;

        if(i==p){

            ww+=add;

        }

    }

    return now>=ww&&res<=0;

}

signed main(){

    cin>>n>>m>>v>>p;

    for(int i=1;i<=n;i++){

        cin>>a[i];

    }

    sort(a+1,a+n+1,cmp);

    int low=1,high=n;

    int ans=0;

    while(low<=high){

        int mid=(low+high)>>1;

        if(judge(mid)){

            low=mid+1;

            ans=mid;

        }

        else{

            high=mid-1;

        }

    }

    cout<<ans<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.396990722003432x):
#include <cstring>

#include <algorithm>

#include <cstdio>

#define int long long

#define ri register int

#define N 100005

using namespace std;

int n,m,v,p,t=0,ans,a[N]= {0};

template <typename T> inline void read(T &x) {

    T c=getchar(),f=0;

    for (; c<48||57<c; c=getchar()) if (c=='-') f=1;

    for (x=0; 48<=c&&c<=57; c=getchar()) x=(x<<3)+(x<<1)+(c^48);

    if (f) x=-x;

}

template <typename T> inline void print(T x) {

    if (x<0) x=-x,putchar('-');

    if (x>9) print(x/10);

    putchar(x%10+48);

}

signed main() {

	read(n),read(m),read(v),read(p),ans=p;

	for (ri i=1; i<=n; i++) read(a[i]);

	sort(a+1,a+1+n),reverse(a+1,a+1+n);

	for (ri i=p+1; i<=n; i++) {

		if (a[i]+m<a[p]) break;

		if (v<=(p-1)+(n-i+1)) ans++;

		else if ((v-p-n+i)*m<=t) ans++;

		else if (((v-p-n+i)*m-t-1)/(i-p)+1+a[p]<=a[i]+m) ans++;

		t+=a[p]-a[i];

	}

	print(ans),putchar('\n');

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, int> pli;

typedef pair<ll, ll> pll;

typedef long double ld;

#define mp make_pair

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 

const int N = 100100;

int n;

ll m, v, p;

ll a[N];

ll pref[N];

 

int main()

{

//	freopen("input.txt", "r", stdin);

//	freopen("output.txt", "w", stdout);

 

	scanf("%d%lld%lld%lld", &n, &m, &v, &p);

	int ans = 0;

	for (int i = 0; i < n; i++)

		scanf("%lld", &a[i]);

	sort(a, a + n);

	reverse(a, a + n); // 将初始分数排序

	for (int i = 0; i < n; i++)

		pref[i + 1] = pref[i] + a[i]; // 前缀和计算区间分数和

	ans = p;

	for (int i = p; i < n; i++) {

		if (a[i] + m < a[p - 1]) break;

		ll cur = v - (n - (i - p + 1)); // 每个评委必须投的票数

		if (cur <= 0) { // 无票可投，第i票有机会被投

			ans++;

			continue;

		}

		if (cur * m <= (i - p + 1) * (a[i] + m) - (pref[i] - pref[p - 1]))

			// cur*m=必须投出的票数

			// (i-p+1)*(a[i]+m)=这(i-p+1)道题目最终的最高分数和

			// pref[i]-pref[p-1]=在[p-1,i)区间内的初始分数和

			// 二者相减=[p-1,i)这些题目所能投的最多票数（？？？？？？？？）

			ans++;

	}

	printf("%d\n", ans);

 

	return 0;

}






















// Faster C++ solution for the same problem (measured speedup: 5.375690817819928x):
#include <cstring>

#include <algorithm>

#include <cstdio>

#define int long long

#define ri register int

#define N 100005

using namespace std;

int n,m,v,p,t=0,ans,a[N]= {0};

template <typename T> inline void read(T &x) {

    T c=getchar(),f=0;

    for (; c<48||57<c; c=getchar()) if (c=='-') f=1;

    for (x=0; 48<=c&&c<=57; c=getchar()) x=(x<<3)+(x<<1)+(c^48);

    if (f) x=-x;

}

template <typename T> inline void print(T x) {

    if (x<0) x=-x,putchar('-');

    if (x>9) print(x/10);

    putchar(x%10+48);

}

signed main() {

	read(n),read(m),read(v),read(p),ans=p;

	for (ri i=1; i<=n; i++) read(a[i]);

	sort(a+1,a+1+n),reverse(a+1,a+1+n);

	for (ri i=p+1; i<=n; i++) {

		if (a[i]+m<a[p]) break;

		if (v<=(p-1)+(n-i+1)) ans++;

		else if ((v-p-n+i)*m<=t) ans++;

		else if (((v-p-n+i)*m-t-1)/(i-p)+1+a[p]<=a[i]+m) ans++;

		t+=a[p]-a[i];

	}

	print(ans),putchar('\n');

    return 0;

}