Блоки данных, считываемые СУБД с жесткого диска, хранятся в оперативной памяти в фиксированном количестве предварительно выделенных буферов. Каждый буфер может содержать один блок данных. Каждый буфер может быть либо свободным, либо занятым некоторыми данными. Когда СУБД собирается считать блок данных с жесткого диска, она должна решить, какой буфер использовать для хранения этого блока данных. Если есть свободные буферы, то используется один из них. Если свободных буферов нет, то необходимо очистить один из занятых буферов, но только в том случае, если он не был заблокирован какой-то частью СУБД.

Выбор буфера для очистки критически важен для производительности СУБД. Было разработано множество алгоритмов выбора. В вашей СУБД будет реализован алгоритм Advanced Buffer Management, который считывает несколько последовательных блоков данных с жесткого диска в последовательные буферы памяти.

Буферы пронумерованы от 1 до N, где N – общее количество буферов. Каждый буфер может находиться в любом из следующих состояний: свободен, занят или заблокирован. Каждому занятому буферу присваивается целое число от 1 до 9 – ценность хранимой в нем информации. Ценность свободных буферов считается равной нулю. Заблокированные буферы не могут быть ни использованы, ни очищены, и их ценность не определена.

Получив запрос на чтение K блоков данных с жесткого диска, диспетчер буферов должен выбрать K последовательных (т.е. с номерами от L до L + K − 1) незаблокированных буферов с минимальной суммарной ценностью или сообщить о том, что это невозможно. Последнее может произойти, если некоторые буферы заблокированы или общее количество буферов меньше K.

Напишите программу, которая моделирует обработку одного запроса в диспетчере буферов по вышеуказанному алгоритму.

Первая строка содержит целые числа N и K (1 ≤ N ≤ 100000; 1 ≤ K ≤ 10000).

Начиная со второй строки, дается описание состояния буферов. Состояние каждого буфера представлено одним символом:

• 0 – соответствующий буфер свободен.
• 1 – соответствующий буфер занят и имеет ценность 1.
• 2 – соответствующий буфер занят и имеет ценность 2.
• ...
• 9 – соответствующий буфер занят и имеет ценность 9.
• * – соответствующий буфер заблокирован.

Эти символы расположены в последовательных строках, сгруппированных по 80 символов в строке без пробелов. Таким образом, каждая строка, начиная со второй, содержит ровно 80 символов (кроме, возможно, последней строки).

Выведите целое число L – номер буфера, начиная с которого нужно выбрать K последовательных буферов для очистки, чтобы гарантировать минимально возможную суммарную ценность. Если существует несколько таких значений L, выведите наименьшее из них.

Выведите 0, если невозможно найти K последовательных незаблокированных буферов.