Buffer Manager

A DBMS (Database Management System) team has built an efficient Lock Manager and now needs a Buffer Manager.

Data blocks read from the hard drive are stored in main memory in a fixed number of pre-allocated buffers. Each buffer holds exactly one data block and is in one of three states:

• free — it holds no useful data; its worthiness is $0$.
• occupied — it holds data with an integer worthiness from $1$ to $9$.
• locked — it is in use by some part of the DBMS, so it can be neither reused nor flushed, and its worthiness is undefined.

When the DBMS reads a data block it must pick a buffer to store it. A free buffer is preferred; if none is free, an occupied non-locked buffer must be flushed. Maximum performance is achieved when several consecutive data blocks are read into consecutive memory buffers, so the manager always allocates one contiguous run of buffers.

Buffers are numbered from $1$ to $N$ ($1 \le N \le 100000$). Given a request to read $K$ data blocks ($1 \le K \le 10000$), the Buffer Manager must choose $K$ consecutive non-locked buffers numbered $L, L+1, \dots, L+K-1$ whose total worthiness (the cost of flushing them) is as small as possible. If several starting positions give the same minimal total, choose the smallest $L$. If no run of $K$ consecutive non-locked buffers exists — which also happens when $N < K$ — the request is impossible.

Write a program that processes one such request.

The first line contains two integers $N$ and $K$ separated by a space.

The buffer states follow, one character per buffer:

• 0 — the buffer is free.
• 1–9 — the buffer is occupied and has that worthiness.
• * — the buffer is locked.

These $N$ characters are written without spaces, grouped $80$ per line. Every line after the first contains exactly $80$ characters, except possibly the last.

Print a single integer $L$: the starting buffer number of the chosen run of $K$ consecutive non-locked buffers with the minimal total worthiness. If several starting positions tie, print the smallest $L$.

Print $0$ if it is impossible to find $K$ consecutive non-locked buffers.