Basketball Together
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1000
Tags: binary search, greedy, sortings

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

Pak Chanek will form zero or more teams from the $$$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$$$. 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$$$.

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 format:
The first line contains two integers $$$N$$$ and $$$D$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le D \le 10^9$$$) — the number of candidate players and the power of the enemy team.

The second line contains $$$N$$$ integers $$$P_1, P_2, \ldots, P_N$$$ ($$$1 \le P_i \le 10^9$$$) — the powers of all candidate players.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

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

Example input:
6 180
90 80 70 60 50 100

Example output:
2

Editorial:
For a team of $$$c$$$ players with a biggest power of $$$b$$$, the total power of the team is $$$b \times c$$$. So for a team with a biggest power of $$$b$$$ to win, it needs to have at least $$$\lceil \frac{D+1}{b} \rceil$$$ players.
For each player $$$i$$$, we can calculate a value $$$f(i)$$$ which means a team that has player $$$i$$$ as its biggest power needs to have at least $$$f(i)$$$ players to win. We can see that the bigger the value of $$$P_i$$$, the smaller the value of $$$f(i)$$$.
We can also see that if a formed team is said to have a fixed biggest power and a fixed number of players, the powers of the players that are less than the biggest power do not affect the total power of the team. So those players can be anyone.
Using the information above, we can form the teams using a greedy method. We iterate through each candidate player starting from the biggest $$$P_i$$$ and form new teams with each next biggest candidate player power as each team's biggest power. We do that while maintaining the total number of extra players required to make all formed teams win. We stop once the number of remaining players is not enough for the total number of extra players required.
Time complexity: $$$O(N \log N)$$$