버퍼 관리자

DBMS(데이터베이스 관리 시스템) 팀이 효율적인 잠금 관리자(Lock Manager)를 완성했고, 이제 버퍼 관리자(Buffer Manager) 가 필요하다.

하드 디스크에서 읽어 온 데이터 블록은 미리 할당된 고정 개수의 버퍼에 저장된다. 각 버퍼는 데이터 블록을 정확히 하나만 담으며, 다음 세 가지 상태 중 하나이다.

• 비어 있음(free) — 유용한 데이터가 없으며, 가치(worthiness)는 $0$이다.
• 사용 중(occupied) — $1$부터 $9$까지의 정수 가치를 가지는 데이터를 담고 있다.
• 잠김(locked) — DBMS의 일부가 사용 중이어서 재사용할 수도 비울 수도 없으며, 가치는 정의되지 않는다.

DBMS가 데이터 블록을 읽을 때는 저장할 버퍼를 골라야 한다. 비어 있는 버퍼가 있으면 그것을 쓰고, 없으면 잠기지 않은 사용 중 버퍼 하나를 비워야 한다. 여러 개의 연속된 데이터 블록을 연속된 메모리 버퍼에 읽어 들일 때 성능이 가장 좋으므로, 관리자는 항상 연속된 버퍼 구간 하나를 할당한다.

버퍼는 $1$번부터 $N$번까지 번호가 매겨져 있다($1 \le N \le 100000$). $K$개의 데이터 블록을 읽으라는 요청($1 \le K \le 10000$)을 받으면, 버퍼 관리자는 $L, L+1, \dots, L+K-1$번의 연속한 잠기지 않은 버퍼 $K$개를 골라 그 가치의 합(= 비우는 데 드는 비용)이 최소가 되도록 해야 한다. 합이 최소가 되는 시작 위치가 여러 개이면 가장 작은 $L$을 고른다. 연속한 잠기지 않은 버퍼 $K$개로 이루어진 구간이 존재하지 않으면($N < K$인 경우도 포함) 요청은 불가능하다.

이러한 요청 하나를 처리하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

이어서 각 버퍼의 상태가 버퍼당 한 문자로 주어진다.

• 0 — 버퍼가 비어 있음.
• 1~9 — 버퍼가 사용 중이며 그 숫자만큼의 가치를 가짐.
• * — 버퍼가 잠김.

이 $N$개의 문자는 공백 없이 한 줄에 $80$자씩 묶여서 주어진다. 첫째 줄을 제외한 모든 줄은 정확히 $80$자를 담으며, 마지막 줄만 예외일 수 있다.

최소 총 가치를 가지는 연속한 잠기지 않은 버퍼 $K$개 구간의 시작 버퍼 번호 $L$을 정수 하나로 출력한다. 같은 최소값을 주는 시작 위치가 여러 개이면 가장 작은 $L$을 출력한다.

연속한 잠기지 않은 버퍼 $K$개를 찾을 수 없으면 $0$을 출력한다.