Taking Out the Trash

Interview

Time limit3sMemory limit2048 MB

Summary

Given n trash bags with weights, find the fewest trips needed when each trip carries one bag or two bags with total weight at most m.

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

Problem

Peter has far too much trash and needs to take all of it out. There are $n$ bags of trash, each with a fixed weight. In one trip, Peter can carry either one bag or two bags, and the total weight of a single trip can be at most $m$ milligrams. What is the minimum number of trips Peter needs to take all the trash out?

Input

The first line contains two integers $n$ and $m$ $(1 \le n \le 5 \cdot 10^5, 1 \le m \le 10^9)$ , the number of bags and the maximum weight Peter can carry in one trip. The next line contains $n$ integers $w_i$ $(1 \le w_i \le m)$ , the weight of each bag in milligrams.

Output

Output the minimum number of trips Peter needs to take all the trash out.

Examples2

Example 1
Input
```
4 1000
100 900 200 900
```
Expected output
```
3
```
Example 2
Input
```
4 10
1 2 3 4
```
Expected output
```
2
```