Diamond Collector

Interview

Time limit2sMemory limit512 MB

Summary

Sort the diamond sizes and pick two disjoint groups with spread at most K to maximize the total count.

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

Problem

Bessie the cow likes shiny things, so in her spare time she took up mining diamonds. She has collected $N$ diamonds of varying sizes, and she wants to display some of them in the two display cases in the barn.

The diamonds inside one case have to be close in size, so Bessie will not put two diamonds in the same case if their sizes differ by more than $K$ . Two diamonds whose sizes differ by exactly $K$ can be displayed in the same case. Each diamond goes in at most one case, and Bessie can leave a diamond out of the display entirely.

Given $K$ , find the largest number of diamonds Bessie can display in the two cases together.

Input

The first line contains $N$ and $K$ . ( $1 \le N \le 50\,000$ , $0 \le K \le 1\,000\,000\,000$ )

Each of the next $N$ lines contains one integer, the size of one diamond. Every size is a positive integer no larger than $1\,000\,000\,000$ .

Output

Print the largest number of diamonds that Bessie can display in the two cases together.

Examples1

Example 1
Input
```
7 3
10
5
1
12
9
5
14
```
Expected output
```
5
```