Balanced matching

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka likes to give Zenik difficult problems. Here is one of them. Marichka gave Zenik an array consisting of \(n\) numbers, and asked him to choose the maximum number of pairs of numbers from it, such that the sum of absolute differences (imbalance) of the chosen pairs is at most \(k\). Each number can be in at most one pair.

For example, there are \(n = 6\) numbers in the array \(a = [2, 5, 3, 4, 7, 10]\), \(k = 4\). Zenik can choose at most two pairs of numbers. One possible choice is (2, 4) and (3, 5). The total imbalance is equal to \(|2 - 4| + |3 - 5| = 2 + 2 = 4\). Since the total imbalance does not exceed \(k\), this is a valid choice of pairs. There are other valid ways to choose pairs, for example, \(|2 - 3| + |5 - 4| = 1 + 1\), but none of these ways will give you more than 2 pairs.

Input

The first line contains two integers \(n\) and \(k\) — the number of elements in the array and the maximum allowed sum of absolute differences.

The second line contains \(n\) integers \(a_i\).

Output

In a single line, print an integer — the answer to the problem.

Constraints

\(1 \le n \le 10^{3}\),

\(1 \le k, a_i \le 10^{9}\).

Samples

Input (stdin) сopy	Output (stdout) сopy
6 2 2 3 8 5 2 10	2

Input (stdin) сopy	Output (stdout) сopy
4 2 5 2 11 8	0

Input (stdin) сopy	Output (stdout) сopy
8 300 0 100 201 302 402 502 1002 1102	3

Notes

In the first example, there are \(n = 6\) numbers in the array, \(a = [2, 3, 8, 5, 2, 10]\) and \(k = 2\). Zenik has two ways to choose two pairs of numbers, which is the maximum answer. One way to do this is (2, 2), (3, 5). Another is (2, 2), (8, 10).

In the second example, there are \(n = 4\) numbers in the array, \(a = [5, 2, 11, 8]\) and \(k = 2\). There are no pairs whose difference does not exceed 2.