Feeding Seals

Interview

Time limit2sMemory limit512 MB

Summary

Each volunteer can carry one or two buckets as long as their combined weight stays within capacity c. Find the minimum number of volunteers needed to move all buckets.

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

Problem

You are in charge of feeding the seals in the Welsh Mountain Zoo. This involves buying buckets of fish and handing them to volunteers who go into the enclosure and share them fairly among the blubbery residents.

The buckets of fish are already laid out. Each volunteer can carry one or two of the buckets, as long as the combined weight of those buckets is small enough.

How many volunteers do you need to deliver all of the fish in one trip?

Input

The first line contains the number of buckets to be delivered, n (1 ≤ n ≤ 105), and the carrying capacity of a volunteer, c (1 ≤ c ≤ 109).
The second line contains the integer weights of the n buckets, w1 ... wn (1 ≤ w ≤ c).

Output

Print the minimum number of volunteers required to deliver all of the buckets of fish.

Examples3

Example 1
Input
```
4 100
44 35 66 67
```
Expected output
```
3
```
Example 2
Input
```
1 10
7
```
Expected output
```
1
```
Example 3
Input
```
3 12
10 5 6
```
Expected output
```
2
```