favorite We need a little bit of your help to keep things running, click on this banner to learn more

A Prize No One Can Win

A Prize No One Can Win

After the festive opening of your new store, the Boutique store for Alternative Paramedicine and Cwakhsahlvereigh, to your disappointment you find out that you are not making as many sales as you had hoped. To remedy this, you decide to run a special offer: you will mark some subset of the n items for sale in your store as participating in the offer, and if people buy exactly two of these items, and the cost of these items is strictly more than x euros, you will give them a free complimentary unicorn horn!

Since you recently found out all your unicorn horns are really narwahl tusks, you decide to rig the offer by picking the participating items in such a way that no one can earn a horn anyway.

To make sure no one becomes suspicious, you want to mark as many items as possible as participating in the offer.


First line contains two integers: n (1n105), the number of items for sale in your store, and x (1x109), the minimum cost specified in the statement. Second line contains n positive integers, each at most 109. These are the prices of the items in the store.


Print the maximum number of items you can mark as part of your special offer, without anyone actually being able to receive a horn.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 6
1 2 3 4 5
Output example #1
Input example #2
5 10
4 8 1 9 7
Output example #2
Input example #3
4 10
1 3 1 7
Output example #3
Input example #4
1 5
Output example #4
Source 2018 Benelux Algorithm Programming Contest (BAPC), Problem A
KALLAX Construction