#P1725B. Basketball Together

    ID: 844 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>binary searchgreedysortings*1000

Basketball Together

Description

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

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

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.

The first line contains two integers NN and DD (1N1051 \le N \le 10^5, 1D1091 \le D \le 10^9) — the number of candidate players and the power of the enemy team.

The second line contains NN integers P1,P2,,PNP_1, P_2, \ldots, P_N (1Pi1091 \le P_i \le 10^9) — the powers of all candidate players.

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

Input

The first line contains two integers NN and DD (1N1051 \le N \le 10^5, 1D1091 \le D \le 10^9) — the number of candidate players and the power of the enemy team.

The second line contains NN integers P1,P2,,PNP_1, P_2, \ldots, P_N (1Pi1091 \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.

Sample Input 1

6 180
90 80 70 60 50 100

Sample Output 1

2

Note

The 11-st team formed is a team containing players 44 and 66. The power of each player in the team becomes 100100. So the total power of the team is 100+100=200>180100 + 100 = 200 > 180.

The 22-nd team formed is a team containing players 11, 22, and 55. The power of each player in the team becomes 9090. So the total power of the team is 90+90+90=270>18090 + 90 + 90 = 270 > 180.