B. Basketball Together | CodeForces Solution

 B. Basketball Together

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A basketball competition is held where the number of players in a team does not have a maximum or minimum limit (not necessarily 5$5$ players in one team for each match). There are N$N$ candidate players in the competition that will be trained by Pak Chanek, the best basketball coach on earth. The i$i$-th candidate player has a power of Pi$P_i$.

Pak Chanek will form zero or more teams from the N$N$ candidate players on the condition that each candidate player may only join in at most one team. Each of Pak Chanek's teams will be sent to compete once with an enemy team that has a power of D$D$. In each match, the team sent is said to defeat the enemy team if the sum of powers from the formed players is strictly greater than D$D$.

One of Pak Chanek's skills is that when a team that has been formed plays in a match, he can change the power of each player in the team to be equal to the biggest player power from the team.

Determine the maximum number of wins that can be achieved by Pak Chanek.

Input

The first line contains two integers N$N$ and D$D$ (1≤N≤105$1\le N\le {10}^5$, 1≤D≤109$1\le D\le {10}^9$) — the number of candidate players and the power of the enemy team.

The second line contains N$N$ integers P1,P2,…,PN$P_1,P_2,\dots ,P_N$ (1≤Pi≤109$1\le P_i\le {10}^9$) — the powers of all candidate players.

Output

A line containing an integer representing the maximum number of wins that can be achieved by Pak Chanek.

Example

input

Copy

6 180
90 80 70 60 50 100

output

Copy

2

Note

The 1$1$-st team formed is a team containing players 4$4$ and 6$6$. The power of each player in the team becomes 100$100$. So the total power of the team is 100+100=200>180$100+100=200>180$.

The 2$2$-nd team formed is a team containing players 1$1$, 2$2$, and 5$5$. The power of each player in the team becomes 90$90$. So the total power of the team is 90+90+90=270>180$90+90+90=270>180$.

	#include <bits/stdc++.h>
	using namespace std;
	#define int long long int
	#define F first
	#define S second
	#define pb push_back
	#define si set <int>
	#define vi vector <int>
	#define pii pair <int, int>
	#define vpi vector <pii>
	#define vpp vector <pair<int, pii>>
	#define mii map <int, int>
	#define mpi map <pii, int>
	#define spi set <pii>
	#define endl "\n"
	#define sz(x) ((int) x.size())
	#define all(p) p.begin(), p.end()
	#define double long double
	#define que_max priority_queue <int>
	#define que_min priority_queue <int, vi, greater<int>>
	#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)
	#define print(a) for(auto x : a) cout << x << " "; cout << endl
	#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl
	#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
	inline int power(int a, int b)
	{
	int x = 1;
	while (b)
	{
	if (b & 1) x *= a;
	a *= a;
	b >>= 1;
	}
	return x;
	}
	template <typename Arg1>
	void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
	template <typename Arg1, typename... Args>
	void __f (const char* names, Arg1&& arg1, Args&&... args)
	{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
	}
	const int N = 200005;
	void solve() {
	int n,d;
	cin>>n>>d;
	deque<int>dq;
	for (int i = 0; i < n; i++)
	{
	int x;
	cin>>x;
	dq.push_back(x);
	}
	sort(dq.begin(),dq.end(),greater<int>());
	int ans=0;
	int rem=n;
	while(!dq.empty()){
	if(rem<=0)break;
	if(dq.front()>d){
	ans++;
	dq.pop_front();
	rem--;
	}
	else{
	int k=(d+dq.front())/dq.front();
	if(k<=rem){
	ans++;
	}
	dq.pop_front();
	rem-=k;
	}
	}
	cout<<ans<<endl;
	}
	int32_t main()
	{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	clock_t z = clock();
	int t = 1;
	// cin >> t;
	while (t--) solve();
	return 0;
	}

Made with ❤ by Raunit Verma Rate Us 5⭐ Here