세탁 바구니 봉인

문제

한 세탁소에서는 접수된 세탁물을 차례대로 바구니에 담는다. 각 세탁물에는 세탁 방법을 나타내는 소문자 표식 하나와 무게가 적혀 있다. 모든 바구니의 허용 무게는 K로 같으며, 하나의 바구니에는 표식이 같은 세탁물만 담을 수 있다. 세탁물은 접수된 순서대로 처리해야 하고, 순서를 바꾸거나 세탁물 하나를 여러 조각으로 나눌 수 없다. 작업대에는 아직 봉인하지 않은 바구니를 최대 하나만 둘 수 있다. 처음에는 작업대에 바구니가 없다. 다음 세탁물을 처리할 때 바구니가 없으면 빈 바구니 하나를 새로 꺼내고 그 세탁물을 담는다. 바구니가 있다면, 그 안의 세탁물과 다음 세탁물의 표식이 같고 다음 세탁물을 넣은 총무게가 K 이하일 때에만 현재 바구니에 담는다. 이 두 조건 중 하나라도 만족하지 않으면 현재 바구니를 봉인한 뒤, 새 바구니를 꺼내 다음 세탁물을 담는다. 한 번 봉인한 바구니는 다시 열거나 작업대로 가져올 수 없다. 따라서 앞에서 같은 표식을 담았던 바구니에 공간이 남아 있더라도 나중의 세탁물을 추가할 수 없다. 현재 바구니의 무게가 정확히 K가 되었다는 이유만으로 즉시 새 바구니를 꺼내지는 않는다. 새 바구니는 실제로 다음 세탁물을 담을 필요가 있을 때에만 꺼낸다. 마지막 세탁물까지 처리하면 작업대에 남아 있는 바구니도 봉인한다. 바구니 하나의 남는 무게는 K에서 그 바구니에 담긴 세탁물의 총무게를 뺀 값이다. 세탁소는 사용한 바구니 수와 모든 사용한 바구니의 남는 무게를 합한 값을 기록하려고 한다. 이 작업에서는 더 적은 바구니를 사용하는 방법을 선택하지 않으며, 정해진 처리 규칙을 그대로 따른다. 입력되는 세탁물은 모두 혼자서 빈 바구니에 들어갈 수 있고, 세탁물은 적어도 하나 존재한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 100,000, 9 ≤ K ≤ 1,000,000이다.
둘째 줄에 길이가 정확히 2N인 문자열 S가 주어진다. 각 i에 대해 S의 2i-1번째 문자는 i번째 세탁물의 표식인 영어 소문자이고, 2i번째 문자는 그 무게를 나타내는 '1'부터 '9'까지의 숫자이다. 무게의 단위는 모두 같다.

출력

사용한 바구니 수와 모든 사용한 바구니의 남는 무게 합을 공백으로 구분하여 한 줄에 정수로 출력한다. 남는 무게가 없으면 합은 0이다.

6 9
a4a5a1b3b6a2

4 15

3 9
c1c1c1

1 6

2 9
a9a9

2 0

출처: Devin.KR 자체 제작