되돌리는 포장 기록

문제

물류 창고에서는 도착한 상자를 순서대로 팔레트에 싣는다. 모든 팔레트의 무게 한도는 K이며, 상자 하나의 무게는 반드시 K 이하이다. 작업대에는 여러 팔레트가 놓일 수 있지만, 새 상자는 현재 사용 중인 마지막 팔레트에만 실을 수 있다. 아직 팔레트가 없다면 첫 번째 팔레트를 만든 뒤 상자를 싣는다. 양의 정수로 된 기록은 그 정수만큼의 무게를 가진 상자가 새로 도착했다는 뜻이다. 마지막 팔레트의 현재 무게에 상자의 무게를 더한 값이 K 이하라면 그 팔레트에 싣는다. K를 넘는다면 새 팔레트를 만들고 그 상자만 싣는다. 무게의 합이 정확히 K인 경우에는 새 팔레트를 만들지 않는다. 앞쪽 팔레트에 여유가 있더라도 그쪽으로 상자를 옮기거나 나누어 싣지 않는다. 정수 0으로 된 기록은 아직 취소되지 않은 상자 중 가장 나중에 도착한 상자 하나를 취소한다는 뜻이다. 취소하면 그 상자를 싣기 직전의 포장 상태로 정확히 돌아간다. 따라서 그 상자를 위해 새 팔레트를 만들었다면 그 팔레트도 사라진다. 취소할 상자가 하나도 없다면 0 기록은 아무 변화도 일으키지 않는다. 취소 기록 자체는 상자로 취급하지 않으며, 이후의 취소 대상에도 포함되지 않는다. 취소한 상자는 다시 나타나지 않는다. 취소 뒤에 새 상자가 도착하면 되돌아간 상태에서 같은 규칙으로 작업을 계속한다. 모든 기록을 주어진 순서대로 처리한 뒤, 남아 있는 팔레트의 개수와 마지막 팔레트에 실린 상자들의 무게 합을 구한다. 상자가 하나도 남지 않았다면 두 값은 모두 0이다. 중간 과정은 출력하지 않는다.

입력

첫째 줄에 기록 수 N과 팔레트의 무게 한도 K가 공백으로 주어진다. N과 K는 정수이며 1≤N≤100,000, 1≤K≤100이다.
둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 각 A_i는 0 또는 1 이상 min(9,K) 이하의 정수이다. 0은 취소 기록이고 양수는 상자의 무게이다.

출력

모든 기록을 처리한 뒤 남은 팔레트의 개수와 마지막 팔레트의 무게 합을 공백으로 구분하여 한 줄에 출력한다. 남은 상자가 없으면 0 0을 출력한다.

8 10
6 5 4 0 3 0 0 2

1 8

5 7
0 7 0 0 0

0 0

출처: Devin.KR 자체 제작