세탁 묶음 넣기

문제

세탁소에는 한 번에 최대 C킬로그램의 세탁물을 넣을 수 있는 세탁기 한 대가 있다. 오늘 처리할 세탁물은 모두 N개의 묶음으로 준비되어 있다. 각 묶음에는 접수한 순서대로 1번부터 N번까지 번호가 붙어 있으며, i번 묶음의 무게는 정수 W_i킬로그램이다. 모든 묶음의 무게는 1킬로그램 이상 C킬로그램 이하이므로 어떤 묶음이든 혼자서는 세탁기에 들어간다. 직원은 접수 순서를 지키기 위해 다음 규칙으로 세탁물을 넣는다. 처음에는 비어 있는 세탁기에 1번 묶음을 넣는다. 이후에는 번호가 증가하는 순서대로 다음 묶음을 확인한다. 현재 세탁기에 들어 있는 무게와 다음 묶음의 무게를 더한 값이 C 이하라면, 그 묶음을 현재 세탁기에 함께 넣는다. 합이 정확히 C인 경우에도 함께 넣을 수 있다. 반대로 두 무게의 합이 C보다 크다면, 직원은 현재 들어 있는 묶음들로 세탁기를 한 번 가동한다. 세탁이 끝난 묶음들을 모두 꺼낸 다음, 방금 확인한 묶음을 비어 있는 세탁기에 넣는다. 그 묶음을 건너뛰고 뒤의 가벼운 묶음을 먼저 확인하는 일은 없으며, 묶음 하나를 나누어 여러 번 세탁하는 일도 없다. N번 묶음까지 모두 넣은 뒤에는 세탁기에 남아 있는 묶음들로 마지막 세탁을 한 번 진행한다. 다만 마지막 묶음을 넣었을 때 무게가 정확히 C가 되었다고 해서 빈 세탁기를 추가로 가동하지는 않는다. 각 묶음은 정확히 한 번 세탁되며, 이미 세탁한 묶음을 뒤의 묶음과 다시 합치지 않는다. 세탁 시간과 세제 사용량은 고려하지 않는다. 정해진 규칙을 그대로 따랐을 때 세탁기를 가동하는 총횟수와 마지막 가동에서 세탁하는 묶음들의 무게 합을 구한다. 묶음이 적어도 하나 주어지므로 마지막 가동은 항상 존재한다.

입력

첫째 줄에 묶음의 수 N과 세탁기의 최대 무게 C가 공백으로 구분되어 주어진다. N과 C는 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000이다.
둘째 줄에 N개의 정수 W_1, W_2, …, W_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ W_i ≤ C이다.

출력

세탁기를 가동하는 총횟수와 마지막 가동의 무게 합을 정수 두 개로 공백으로 구분하여 출력한다.

6 10
4 6 3 5 7 2

3 9

3 8
3 2 3

1 8

1 1
1

1 1

출처: Devin.KR 자체 제작