D. Расписание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иван учится в Берляндском Государственном Университете (БГУ). В берляндской неделе n дней, в каждый из них у Ивана могут быть занятия в университете.

В одном дне m рабочих часов, каждое занятие в университете длится ровно час. Если в какой-то день первое занятие у Ивана в течение i-го часа, а последнее — в течение j-го, то он тратит ровно j - i + 1 час в университете в этот день. Если в какой-либо день нет занятий, то Иван остается дома и проводит 0 часов в университете, соответственно.

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

По заданным n, m, k и расписанию Ивана определите, какое минимальное количество часов он может провести в университете за неделю, если он не может пропустить больше k занятий.

Входные данные

В первой строке записаны три целых числа n, m и k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 500) — количество дней в берляндской неделе, количество рабочих часов в каждый день и количество занятий, которые Иван может пропустить, соответственно.

Затем следуют n строк, i-я содержит бинарную строку длины m. Если j-й символ i-й строки равен 1, то у Ивана есть занятие в i-й день в течение j-го часа (и если равен 0, то занятия нет).

Выходные данные

Выведите минимальное количество часов, которые Ивану придется провести в университете, если он не может пропустить больше k занятий.

Примеры
Входные данные
2 5 1
01001
10110
Выходные данные
5
Входные данные
2 5 0
01001
10110
Выходные данные
8
Примечание

В первом примере Иван может пропустить любое из двух занятий в первый день, поэтому он потратит 1 час в первый день и 4 часа во второй.

Во втором примере Иван не может пропустить ни одного занятия, поэтому он потратит 4 часа в оба дня.