Cat Cafe

Interview

Time limit2sMemory limit1024 MB

Summary

Pair up cats so each pair's total weight is at most K, and find the maximum number of pairs that can be formed.

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

Problem

Chanwoo is going to a cat cafe with his friends.

The cat cafe has $N$ cats. The weight of the $i$ -th cat is $w\_i$ . Chanwoo and his friends all love cats, so each person becomes happy when they hold exactly $2$ cats on their lap. However, Chanwoo and his frail friends cannot hold up if the total weight of the two cats they hold exceeds $K$ .

Given the weight of each cat and the maximum weight $K$ that one person can bear, find the maximum number of people who can be happy.

Input

The first line contains integers $N$ and $K$ , separated by a space. ( $1 \leq N \leq 5\,000$ ; $1 \leq K \leq 10^9$ )

The second line contains $N$ integers $w\_1, w\_2, \dotsm, w\_N$ , separated by spaces. ( $1 \leq w\_i \leq K$ )

Output

Print the maximum number of people who can be happy.

Examples3

Example 1
Input
```
5 20
8 16 11 2 4
```
Expected output
```
2
```
Example 2
Input
```
6 10
9 5 6 7 4 3
```
Expected output
```
2
```
Example 3
Input
```
4 100
100 99 98 97
```
Expected output
```
0
```