stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 100; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.232611286112228x):
#include<bits/stdc++.h>

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 40; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

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

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 100; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2822156425250137x):
#include<bits/stdc++.h>

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 30; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

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

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 100; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2926234032453796x):
#include<bits/stdc++.h>

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 28; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

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

using namespace std;



int main() {

    int N;

    cin >> N;

    vector<int> vec(N);

    for (auto& i : vec) cin >> i;



    double l = 0., r = 1.0;

    for (int c = 0; c < 100; c++) {

        double m = (l + r) / 2.0;

        set<int> s;

        s.insert(1);



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

            int lo_n = ceil((1.0 - m) * (double)vec[i]);

            int up_n = (1.0 + m) * vec[i];



            set<int> ns;

            for (auto j : s) {

                int v = up_n / j;

                int u = ceil((double)lo_n / j);

                for (; u <= v; u++) if (u != 0) ns.insert(j * u);

            }



            s = ns;

        }



        if (s.size() > 0) r = m;

        else l = m;

    }



    printf("%.10f\n", l);



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3099517942316126x):
#include <bits/stdc++.h>

using namespace std;



int main() {

    int N;

    cin >> N;

    vector<int> vec(N);

    for (auto& i : vec) cin >> i;



    double l = 0., r = 1.0;

    for (int c = 0; c < 27; c++) {

        double m = (l + r) / 2.0;

        set<int> s;

        s.insert(1);



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

            int lo_n = ceil((1.0 - m) * (double)vec[i]);

            int up_n = (1.0 + m) * vec[i];



            set<int> ns;

            for (auto j : s) {

                int v = up_n / j;

                int u = ceil((double)lo_n / j);

                for (; u <= v; u++) if (u != 0) ns.insert(j * u);

            }



            s = ns;

        }



        if (s.size() > 0) r = m;

        else l = m;

    }



    printf("%.10f\n", l);



    return 0;

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

#include <algorithm>

#include <utility>

#include <queue>

#include <cstdio>

#include <iostream>

#include <string>

#include <string.h>

#include <stdio.h>

#include <complex>



using namespace std;

typedef pair<int, int> PII;

typedef pair<int, PII> TIII;

#define PB push_back

#define MP make_pair

#define MT(a,b,c) MP(a, MP(b, c))

#define T1 first

#define T2 second.first

#define T3 second.second

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

#define REP(i,n)  FOR(i,0,n)

int a[20];

int n;



bool DFS(int k, int m, double r){

	int s = ceil(a[k]-a[k]*r);

	if(s==0)s=1;

	int e = ceil(a[k]+a[k]*r);

	for(int p = ((s-1)/m+1)*m; p<e; p+=m)

		if(k==n-1)return true;

		else if(DFS(k+1, p, r))return true;



	return false;

}



bool C(double r){

	return DFS(0,1,r);

}



int main(){

	cin>>n;

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

	double u=1.0, l=0.0;

	while(u-l>1e-9){

		double mid = (u+l)*0.5;

		if(C(mid))u=mid;

		else l = mid;

	}

	printf("%.10f\n", u);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.848091325811166x):
#include <stdio.h>

#include <cmath>

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

#define REP(i,n)  FOR(i,0,n)

int a[20];

int n;



bool DFS(int k, int m, double r){

	int s=ceil(a[k]-a[k]*r);

	if(s==0)s=1;

	int e=ceil(a[k]+a[k]*r);

	for(int p=((s-1)/m+1)*m;p<e;p+=m)

		if(k==n-1)return true;

		else if(DFS(k+1,p,r))return true;

	return false;

}



bool C(double r){

	return DFS(0,1,r);

}



int main(){

	scanf("%d",&n);

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

	double u=1.0, l=0.0;

	while(u-l>1e-9){

		double mid=(u+l)*0.5;

		if(C(mid))u=mid;

		else l=mid;

	}

	printf("%.10f\n",u);

	return 0;

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

#include <algorithm>

#include <utility>

#include <queue>

#include <cstdio>

#include <iostream>

#include <string>

#include <string.h>

#include <stdio.h>

#include <complex>



using namespace std;

typedef pair<int, int> PII;

typedef pair<int, PII> TIII;

#define PB push_back

#define MP make_pair

#define MT(a,b,c) MP(a, MP(b, c))

#define T1 first

#define T2 second.first

#define T3 second.second

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

#define REP(i,n)  FOR(i,0,n)

int a[20];

int n;



bool DFS(int k, int m, double r){

	int s = ceil(a[k]-a[k]*r);

	if(s==0)s=1;

	int e = ceil(a[k]+a[k]*r);

	for(int p = ((s-1)/m+1)*m; p<e; p+=m)

		if(k==n-1)return true;

		else if(DFS(k+1, p, r))return true;



	return false;

}



bool C(double r){

	return DFS(0,1,r);

}



int main(){

	cin>>n;

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

	double u=1.0, l=0.0;

	while(u-l>1e-9){

		double mid = (u+l)*0.5;

		if(C(mid))u=mid;

		else l = mid;

	}

	printf("%.10f\n", u);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.867363056006956x):
#include <stdio.h>

#include <cmath>

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

#define REP(i,n)  FOR(i,0,n)

int a[20];

int n;



bool DFS(int k, int m, double r){

	int s=ceil(a[k]*(1-r));

	if(s==0)s=1;

	int e=ceil(a[k]*(1+r));

	for(int p=((s-1)/m+1)*m;p<e;p+=m)

		if(k==n-1)return true;

		else if(DFS(k+1,p,r))return true;

	return false;

}



int main(){

	scanf("%d",&n);

	REP(i,n)scanf("%d",a+i);

	double u=1.0, l=0.0;

	REP(i,30){

		double m=(u+l)*0.5;

		if(DFS(0,1,m))u=m;

		else l=m;

	}

	printf("%.9f\n",u);

	return 0;

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

#include <algorithm>

#include <utility>

#include <queue>

#include <cstdio>

#include <iostream>

#include <string>

#include <string.h>

#include <stdio.h>

#include <complex>



using namespace std;

typedef pair<int, int> PII;

typedef pair<int, PII> TIII;

#define PB push_back

#define MP make_pair

#define MT(a,b,c) MP(a, MP(b, c))

#define T1 first

#define T2 second.first

#define T3 second.second

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

#define REP(i,n)  FOR(i,0,n)

int a[20];

int n;



bool DFS(int k, int m, double r){

	int s = ceil(a[k]-a[k]*r);

	if(s==0)s=1;

	int e = ceil(a[k]+a[k]*r);

	for(int p = ((s-1)/m+1)*m; p<e; p+=m)

		if(k==n-1)return true;

		else if(DFS(k+1, p, r))return true;



	return false;

}



bool C(double r){

	return DFS(0,1,r);

}



int main(){

	cin>>n;

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

	double u=1.0, l=0.0;

	while(u-l>1e-9){

		double mid = (u+l)*0.5;

		if(C(mid))u=mid;

		else l = mid;

	}

	printf("%.10f\n", u);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.897858101613896x):
#include <stdio.h>

#include <cmath>

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

#define REP(i,n)  FOR(i,0,n)

int a[20];

int n;



bool DFS(int k, int m, double r){

	int s=ceil(a[k]*(1-r));

	int e=ceil(a[k]*(1+r));

	for(int p=((s-1)/m+1)*m;p<e;p+=m)

		if(k==n-1)return true;

		else if(DFS(k+1,p,r))return true;

	return false;

}



int main(){

	scanf("%d",&n);

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

	double u=1.0,l=0.0;

	REP(i,30){

		double m=(u+l)*0.5;

		if(DFS(0,1,m))u=m;

		else l=m;

	}

	printf("%.9f\n",u);

	return 0;

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

#include <vector>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

vector<int> DP[5001];



int main()

{

	int N, K; cin >> N >> K;

	vector<int>a(N);

	vector<bool>b(N);



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

		cin >> a[i];

	}

	sort(a.begin(), a.end());

	reverse(a.begin(), a.end());



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

		if (a[i] >= K) {

			b[i] = true;

			continue;

		}

		for (int j = K-1; j >= 0; j--) {

			if (DP[j].size() != 0) {

				if (j + a[i] >= K) {

					while(DP[j].size()){

						if (DP[j][0] == -1) {

							DP[j].erase(DP[j].begin());

							continue;

						}

						b[DP[j][0]] = true;

						DP[j].erase(DP[j].begin());

					}

					b[i] = true;

					DP[j].push_back(-1);

					break;

				}

				else {

					for (int k = 0; k < DP[j].size(); k++) {

						DP[j + a[i]].push_back(DP[j][k]);

					}

					DP[j + a[i]].push_back(i);

					break;

				}

			}

		}

		DP[a[i]].push_back(i);

	}



	int ans = 0;

	for (int i = 0; i < N; i++)if (b[i] == false) {

		ans++;

	}

	cout << ans << endl;



    return 0;

}


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

#include <vector>

#include <algorithm>

using namespace std;



int main() {

	int n,k;

    cin>>n>>k;

    vector<int>a(n);

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

    sort(a.begin(),a.end());

    reverse(a.begin(),a.end());



    int cnt=0,sum=0;

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

        if(sum+a[i]<k){

            sum+=a[i];

            cnt++;

        }

        else cnt=0;

    }



    cout<<cnt<<endl;



	return 0;

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

#include <vector>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

vector<int> DP[5001];



int main()

{

	int N, K; cin >> N >> K;

	vector<int>a(N);

	vector<bool>b(N);



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

		cin >> a[i];

	}

	sort(a.begin(), a.end());

	reverse(a.begin(), a.end());



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

		if (a[i] >= K) {

			b[i] = true;

			continue;

		}

		for (int j = K-1; j >= 0; j--) {

			if (DP[j].size() != 0) {

				if (j + a[i] >= K) {

					while(DP[j].size()){

						if (DP[j][0] == -1) {

							DP[j].erase(DP[j].begin());

							continue;

						}

						b[DP[j][0]] = true;

						DP[j].erase(DP[j].begin());

					}

					b[i] = true;

					DP[j].push_back(-1);

					break;

				}

				else {

					for (int k = 0; k < DP[j].size(); k++) {

						DP[j + a[i]].push_back(DP[j][k]);

					}

					DP[j + a[i]].push_back(i);

					break;

				}

			}

		}

		DP[a[i]].push_back(i);

	}



	int ans = 0;

	for (int i = 0; i < N; i++)if (b[i] == false) {

		ans++;

	}

	cout << ans << endl;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.128280550624963x):
#include <bits/stdc++.h>

using namespace std;

#define rrep(n) for(int i=n-1;i+1;i--)

int n,k,sum,cnt;

main() {

	cin>>n>>k;

	vector<int>a(n);

	rrep(n)cin>>a[i];

	sort(a.begin(),a.end());

	rrep(n){

		if(sum+a[i]<k){

			sum+=a[i];

			cnt++;

		}

		else cnt=0;

	}

	cout<<cnt<<endl;

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

#include <vector>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

vector<int> DP[5001];



int main()

{

	int N, K; cin >> N >> K;

	vector<int>a(N);

	vector<bool>b(N);



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

		cin >> a[i];

	}

	sort(a.begin(), a.end());

	reverse(a.begin(), a.end());



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

		if (a[i] >= K) {

			b[i] = true;

			continue;

		}

		for (int j = K-1; j >= 0; j--) {

			if (DP[j].size() != 0) {

				if (j + a[i] >= K) {

					while(DP[j].size()){

						if (DP[j][0] == -1) {

							DP[j].erase(DP[j].begin());

							continue;

						}

						b[DP[j][0]] = true;

						DP[j].erase(DP[j].begin());

					}

					b[i] = true;

					DP[j].push_back(-1);

					break;

				}

				else {

					for (int k = 0; k < DP[j].size(); k++) {

						DP[j + a[i]].push_back(DP[j][k]);

					}

					DP[j + a[i]].push_back(i);

					break;

				}

			}

		}

		DP[a[i]].push_back(i);

	}



	int ans = 0;

	for (int i = 0; i < N; i++)if (b[i] == false) {

		ans++;

	}

	cout << ans << endl;



    return 0;

}


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

#include <vector>

#include <algorithm>

#include <string>

using namespace std;



int N, K;

int A[5001];



void insertionSort(int g) {

	for (int i = g; i < N; i++) {

		int v = A[i];

		int j = i - g;



		while (j >= 0 && A[j] < v) {

			A[j + g] = A[j];

			j -= g;

		}

		A[j + g] = v;

	}

}



void shellSort() {

	vector<int>G;

	for (int h = 1;;) {

		if (h > N)break;

		G.push_back(h);

		h = 3 * h + 1;

	}



	for (int i = G.size() - 1; i >= 0; i--) {

		insertionSort(G[i]);

	}

}



int main()

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	cin >> N >> K;

	for (int i = 0; i < N; i++)cin >> A[i];



	shellSort();



	int sum = 0, cnt = 0;

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

		if (sum + A[i] < K) {

			sum += A[i];

			cnt++;

		}

		else cnt = 0;

	}



	cout << cnt << endl;



    return 0;

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

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<long long,long long> pll;

#define ep emplace_back

#define pb push_back

#define mp make_pair

#define rep(i,n) for(int i=0;i<(n);++i)

constexpr int mod=1000000007;

constexpr int mod1=998244353;

vector<int> dx={0,1,0,-1},dy={-1,0,1,0};

bool inside(int y,int x,int h,int w){

	if(y<h && y>=0 && x<w && x>=0) return true;

	return false;

}











int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	int n,k;cin >> n >> k;

	vector<int> a(n);

	rep(i,n) cin >> a.at(i);

	sort(a.begin(),a.end());

	vector<vector<int>> dp(n + 2, vector<int>(5010));

	dp[0][0] = 1;

	int ng = 0,ok = n + 1;

	while(ok - ng > 1){

		int mid = (ok + ng) / 2;

		if(a.at(mid - 1) >= k){

			ok = mid;

			continue;

		}

		rep(i,n + 1){

			rep(j,k + 1){

				dp[i][j] = 0;

			}

		}

		dp[0][0] = 1;

		rep(i,n){

			rep(j,k + 1){

				if(i + 1 != mid && j - a.at(i) >= 0) dp[i + 1][j] |= dp[i][j - a.at(i)];

				dp[i + 1][j] |= dp[i][j];

			}

		}

		bool flg = false;

		for(int i = k - a.at(mid - 1); i < k; i++){

			if(dp[n][i]){

				flg = true;

				break;

			}

		}

		if(flg) ok = mid;

		else ng = mid;

	}

	cout << ng << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.2102892726332108x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<long long,long long> pll;

#define ep emplace_back

#define pb push_back

#define mp make_pair

#define rep(i,n) for(int i=0;i<(n);++i)

constexpr int mod=1000000007;

constexpr int mod1=998244353;

vector<int> dx={0,1,0,-1},dy={-1,0,1,0};

bool inside(int y,int x,int h,int w){

	if(y<h && y>=0 && x<w && x>=0) return true;

	return false;

}











int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	int n,k;cin >> n >> k;

	vector<int> a(n);

	rep(i,n) cin >> a.at(i);

	sort(a.begin(),a.end());

	int ng = 0,ok = n + 1;

	while(ok - ng > 1){

		int mid = (ok + ng) / 2;

		if(a.at(mid - 1) >= k){

			ok = mid;

			continue;

		}

		vector<bitset<5010>> dp(n + 1);

		dp[0].set(0);

		rep(i,n){

			if(i == mid - 1) dp[i + 1] |= dp[i];

			else dp[i + 1] |= dp[i] | (dp[i] << a.at(i));

		}

		bool flg = false;

		for(int i = k - a.at(mid - 1); i < k; i++){

			if(dp[n][i]){

				flg = true;

				break;

			}

		}

		if(flg) ok = mid;

		else ng = mid;

	}

	cout << ng << endl;

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

#define ll long long

#define maxn 100005

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define pb push_back

#define pii pair<int,int>

using namespace std;



int n,k;

int a[5005];



bool Check(int mid){

    if(a[mid]>=k) return 1;

    bitset<maxn> bs;

    bs[0]=1;

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

        if(i!=mid) bs|=bs<<a[i];

    }

    for(int i=k-1;i>=k-a[mid];i--){

        if(bs[i]) return 1;

    }

    return 0;

}



int main(){



    cin>>n>>k;

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

        cin>>a[i];

    }

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

    int L=1,R=n,mid;

    while(L<=R){

        mid=L+R>>1;

        if(Check(mid)) R=mid-1;

        else L=mid+1;

    }

    cout<<R<<endl;





}






// Faster C++ solution for the same problem (measured speedup: 1.1460365159637385x):
#include<bits/stdc++.h>

#define ll long long

#define maxn 100005

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define pb push_back

#define pii pair<int,int>

using namespace std;



int n,k;

int a[5005];



bool Check(int mid){

    if(a[mid]>=k) return 1;

    bitset<5005> bs;

    bs[0]=1;

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

        if(a[i]>5000) break;

        if(i!=mid) {

            bs|=bs<<a[i];

        }

    }

    for(int i=k-1;i>=k-a[mid];i--){

        if(bs[i]) return 1;

    }

    return 0;

}



int main(){



    cin>>n>>k;

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

        cin>>a[i];

    }

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

    int L=1,R=n,mid;

    while(L<=R){

        mid=L+R>>1;

        if(Check(mid)) R=mid-1;

        else L=mid+1;

    }

    cout<<R<<endl;





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

using namespace std;

const int N = 5010;

bool canleft[N][N], canright[N][N];

int n, K;

int a[N];

bool can[N];

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0), cout.tie(0);

	cin >> n >> K;

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

		cin >> a[i];

	canleft[0][0] = 1;

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

		for(int j = 0; j < N; j++){

			canleft[i][j] = canleft[i - 1][j];

			if(j >= a[i])

				canleft[i][j] |= canleft[i - 1][j - a[i]];

		}

	}

	canright[n + 1][0] = 1;

	for(int i = n; i >= 2; i--){

		for(int j = 0; j < N; j++){

			canright[i][j] = canright[i + 1][j];

			if(j >= a[i])

				canright[i][j] |= canright[i + 1][j - a[i]];

		}

	}

	int cnt = 0;

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

		bool nece = false;

		vector<int> A, B;

		for(int j = 0; j < N; j++)

			if(canleft[i - 1][j]) A.push_back(j);

		for(int j = 0; j < N; j++)

			if(canright[i + 1][j]) B.push_back(j);

		for(int val : A){

			int tmp = K - a[i] - val;

			vector<int>::iterator it = lower_bound(B.begin(), B.end(), tmp);

			if(it != B.end()){

				if((*it) + val < K)

					nece = true;

			}

		}

		if(!nece) cnt++;

	}

	cout << cnt << "\n";

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1296119559146856x):
#include <bits/stdc++.h>

using namespace std;

bitset<5005> pref[5005], suff[5005];

int a[5005];

int main(){

    int n, k;

    scanf("%d%d", &n, &k);

    pref[0][0] = suff[n+1][0] = 1;

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

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

        for(int j=0;j<=k;j++){

            if(pref[i-1][j]){

                if(j+a[i] <= k) pref[i][j+a[i]] = 1;

                pref[i][j] = 1;

            }

        }

    }

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

        for(int j=0;j<=k;j++){

            if(suff[i+1][j]){

                if(j+a[i] <= k) suff[i][j+a[i]] = 1;

                suff[i][j] = 1;

            }

        }

    }

    int ans = 0;

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

        if(a[i] >= k) continue;

        int l = k-a[i], r = k-1, sum = 0, ok = 1;

        for(int j=l;j<=r;j++) if(suff[i+1][j]) sum++;

        for(int j=0;j<=k-1;j++){

            if(pref[i-1][j] && sum > 0){

                ok = 0;

                break;

            }

            if(l > 0){

                l--;

                if(suff[i+1][l]) sum++;

            }

            if(suff[i+1][r]) sum--;

            r--;

        }

        if(ok) ans++;

    }

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

}