A Prize No One Can Win

Interview

Time limit1.5sMemory limit512 MB

Summary

Pick a largest subset of item prices such that no pair has a sum strictly greater than X, and print its size.

Level: Medium5 of 10
Topics: Array, Sorting, Two pointers, Greedy
Solved: No attempts yet

Problem

After the festive opening of your new store, the Boutique store for Alternative Paramedicine and Cwakhsahlvereigh, you find to your disappointment 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 narwhal 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.

Input

On the first line, two integers: 1 ≤ n ≤ 105, the number of items for sale in your store, and 1 ≤ X ≤ 109, the minimum cost specified in the statement.
On the second line, n positive integers, each at most 109. These are the prices of the items in the store.

Output

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

Examples4

Example 1
Input
```
5 6
1 2 3 4 5
```
Expected output
```
3
```
Example 2
Input
```
5 10
4 8 1 9 7
```
Expected output
```
2
```
Example 3
Input
```
4 10
1 3 1 7
```
Expected output
```
4
```
Example 4
Input
```
1 5
6
```
Expected output
```
1
```