Remote Training on Programming

Имеется состав из 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) и (1 £ M £ 10⁶).

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

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

Примеры

Входные данные	Выходные данные
1 6 101010101110111110101010111110101111000000111111111011	1
2 2 011111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111011111111111111111	22

 

Условия всех задач XVI межвузовской олимпиады в одном файле