1957. Поезд

Имеется состав из `N` плацкартных вагонов. Вагоны стандартные: по 54 места в каждом, места разделены на 9 блоков. Расположение мест и вагонов показано на рисунке:

Вам требуется разместить в вагонах `М` человек так, чтобы расстояние между двумя самыми удалёнными друг от друга людьми было минимальным. Расстояние измеряется по прямой вдоль вагонов. Будем считать, что расстояние между местами в одном блоке равно нулю. Например, расстояние между любой парой мест 1, 2, 3, 4, 53 или 54 равно нулю. Между местами в соседних блоках расстояние равно 1. Например, между 1 и 6, 53 и 7. Расстояние между вагонами равно 6. То есть расстояние между местом 33 первого вагона и местом 1 второго вагона равно 6.

Рассмотрим пример из одного вагона (первый тест):

Серым помечены занятые места, а белым – свободные. Нужно разместить 6 человек. Оптимально будет занять места 30, 32, 37, 38, 39, 40 в конце вагона. Наибольшее расстоянием будет равно 1.

В первой строке входного файла содержатся 2 целых числа `N` (`1\ ≤\ N\ ≤\ 10\ 000`) и `M` (`1\ ≤\ M\ ≤\ 10^6`).

Каждая из следующих `N` строк содержит по 54 символа — информацию о местах в соответствующих вагонах: 0 — место свободно, 1 — занято.

Выведите в выходной файл одно искомое число, либо `-1`, если разместить всех людей невозможно.

1 6
101010101110111110101010111110101111000000111111111011

1

2 2
011111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111011111111111111111

22