Problem L
Taking Out the Trash
Peter has way too much trash and he needs to take it all out.
Specifically, there are $n$ bags of trash each with a specific weight. Peter can hold either one or two bags of trash per trip, and he can carry a maximum total of $m$ milligrams of trash in a single trip. What is the minimum number of trips Peter needs to take to take out all the trash?
Input
The input starts with two integers $n$ $(1 \le n \le 5 \cdot 10^5)$ and $m$ $(1 \le m \le 10^9)$, the number of bags of trash and the maximum weight of trash Peter can carry.
The next line contains $n$ integers, $w_i$ $(1 \le w_i \le m)$, the weight of each bag of trash in milligrams.
Output
Output the minimum number of trips Peter needs to make to take out all the trash.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1000 100 900 200 900 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 10 1 2 3 4 |
2 |
