쓰레기 버리기

면접 대비

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

요약

각 가방의 무게가 주어졌을 때, 한 번에 가방 한 개 또는 두 개를 총 무게 m 이하로 옮긴다면 필요한 최소 횟수를 구합니다.

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

문제

피터는 버릴 쓰레기가 너무 많아서 전부 내다 버려야 한다. 쓰레기 봉지는 $n$ 개이며, 봉지마다 무게가 정해져 있다. 피터는 한 번에 봉지를 한 개 또는 두 개만 들 수 있고, 한 번에 옮길 수 있는 무게의 합은 최대 $m$ 밀리그램이다. 모든 쓰레기를 버리는 데 필요한 최소 횟수는 얼마인가?

입력

첫 줄에 봉지의 개수 $n$ 과 피터가 한 번에 들 수 있는 최대 무게 $m$ 이 주어진다 $(1 \le n \le 5 \cdot 10^5, 1 \le m \le 10^9)$ . 둘째 줄에는 각 봉지의 무게 $w_i$ (밀리그램)가 $n$ 개 주어진다 $(1 \le w_i \le m)$ .

출력

피터가 모든 쓰레기를 버리는 데 필요한 최소 횟수를 출력한다.

예제2

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