출발 대기 상자

문제

택배 작업대에는 물품을 담는 상자 하나가 놓여 있다. 작업자는 기록 장치에 남은 문자를 왼쪽부터 하나씩 읽으며 물품을 담거나 상자를 출발시킨다. 각 상자에 담을 수 있는 물품의 무게 합은 정수 C 이하이며, 처음 작업대에 놓인 상자는 비어 있다. 물품을 담는 순서는 기록에 나타난 순서와 같아야 한다. 기록은 숫자 문자로만 이루어진 문자열이다. '1'부터 '9'까지의 문자는 그 숫자만큼의 무게를 가진 물품 하나가 도착했다는 뜻이다. 기록에 등장하는 모든 물품의 무게는 C 이하이다. 물품이 도착하면 현재 상자에 담긴 무게와 새 물품의 무게를 더한다. 그 합이 C 이하이면 현재 상자에 새 물품을 담는다. 합이 C보다 크면 현재 상자를 먼저 출발시키고, 새 빈 상자를 작업대에 놓은 뒤 도착한 물품을 그 상자에 담는다. 이미 담은 물품을 다른 상자로 옮기거나 도착한 물품을 나중으로 미룰 수는 없다. 문자 '0'은 출발 지시를 뜻한다. 이 지시를 읽었을 때 현재 상자에 물품이 하나 이상 있으면 그 상자를 출발시키고 새 빈 상자를 놓는다. 현재 상자가 비어 있으면 아무 일도 일어나지 않는다. 따라서 빈 상자는 출발한 상자의 수에 포함되지 않는다. 무게 합이 정확히 C가 된 상자도 즉시 출발하지는 않는다. 이후 물품을 담을 수 없게 되거나 출발 지시를 읽을 때까지 작업대에 남는다. 기록을 모두 읽으면 작업을 그대로 끝낸다. 마지막에 작업대에 남은 상자는 물품이 들어 있어도 자동으로 출발시키지 않는다. 출발한 상자의 수, 출발한 상자 중 가장 무거운 상자의 무게 합, 마지막에 작업대에 남은 물품의 무게 합을 구해야 한다. 출발한 상자가 하나도 없으면 가장 무거운 상자의 무게 합은 0으로 정한다. 가장 무거운 상자가 여러 개여도 그 무게 합만 구하므로 별도의 순서를 정하지 않는다.

입력

첫째 줄에 기록의 길이 N과 상자의 무게 제한 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 1 ≤ N ≤ 100,000, 1 ≤ C ≤ 9이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 '0'부터 C를 나타내는 숫자 문자까지 중 하나이다. '0'은 출발 지시이며, 나머지 문자는 해당 무게의 물품 도착을 뜻한다.

출력

출발한 상자의 수, 출발한 상자 중 가장 큰 무게 합, 작업 종료 시 현재 상자에 담긴 무게 합을 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 출발한 상자가 없으면 두 번째 값은 0이다. 현재 상자가 비어 있으면 세 번째 값은 0이다.

10 7
3402501604

3 7 4

7 5
2231054

3 5 4

6 9
000123

0 0 6

출처: Devin.KR 자체 제작