Taking Out the Trash

시간 제한3초메모리 제한2048 MB

요약

봉지 무게와 한 번에 들 수 있는 최대 무게가 주어질 때, 한 번에 한 봉지 또는 두 봉지를 옮겨 모든 쓰레기를 버리는 최소 횟수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 투 포인터, 정렬
정답자: 아직 제출이 없습니다

문제

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?

입력

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 the minimum number of trips Peter needs to make to take out all the trash.

예제2

예제 1
입력
```
4 1000
100 900 200 900
```
예상 출력
```
3
```
예제 2
입력
```
4 10
1 2 3 4
```
예상 출력
```
2
```