출발하는 운반 수레

문제

물류 창고의 포장 구역에는 출고할 상자 N개가 한 줄로 놓여 있다. 상자는 앞에서부터 1번부터 N번까지 번호가 붙어 있으며, i번 상자의 무게는 W_i이다. 작업자는 수레 한 대를 이용하여 이 상자들을 출발 지점에서 인계 구역으로 옮긴다. 수레에 한 번에 실을 수 있는 상자 무게의 합은 C 이하이다. 모든 상자의 무게는 양수이며 C 이하이므로, 상자 하나를 빈 수레에 싣지 못하는 경우는 없다. 작업을 시작할 때 수레는 비어 있고, 작업자는 반드시 상자의 번호가 작은 순서대로 상자를 처리한다. 다음 상자를 현재 수레에 실었을 때 무게의 합이 C 이하라면 그 상자를 바로 싣는다. 무게의 합이 정확히 C가 되는 경우에도 상자를 실을 수 있다. 이때 수레가 가득 찼다는 이유만으로 즉시 출발하지는 않으며, 다음 상자를 처리할 때 같은 규칙을 다시 적용한다. 다음 상자를 실었을 때 무게의 합이 C를 넘는다면, 작업자는 현재 수레에 실린 상자들을 인계 구역으로 운반한다. 이를 운반 한 번으로 센다. 인계 구역에서는 실린 상자를 모두 내리고, 작업자는 빈 수레를 가지고 출발 지점으로 돌아온다. 그런 다음 방금 싣지 못했던 상자를 빈 수레에 싣고 다음 번호의 상자를 처리한다. 수레가 출발 지점으로 돌아오는 이동은 별도의 운반 횟수로 세지 않는다. 마지막 상자까지 처리한 뒤 수레에 상자가 남아 있다면, 그 상자들도 인계 구역으로 운반하며 횟수를 한 번 더 센다. 작업 도중 상자의 순서를 바꾸거나, 상자를 나누거나, 이미 실은 상자를 미리 내려놓을 수는 없다. 또한 자리가 남았더라도 뒤쪽 상자를 먼저 골라 실을 수 없다. 이 절차를 그대로 따를 때 모든 상자를 옮기는 데 필요한 운반 횟수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 상자의 수 N과 수레의 무게 한도 C가 공백으로 구분되어 주어진다. 둘째 줄에 W_1부터 W_N까지가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 1 ≤ W_i ≤ C이다.

출력

주어진 절차에 따른 총 운반 횟수를 정수 하나로 출력한다.

6 10
4 6 3 8 2 5

4

4 12
2 3 1 6

1

3 5
5 5 5

3

출처: Devin.KR 자체 제작