시간표

Ivan은 Berland State University (BSU)의 학생이다. Berland의 한 주는 n일이며, Ivan은 그 각 날에 대학교에서 수업이 있을 수도 있다.

Berland의 하루에는 m개의 근무 시간이 있으며, 대학교의 각 수업은 정확히 한 시간 동안 진행된다. 어떤 날 Ivan의 첫 수업이 i-th시간에 있고 마지막 수업이 j-th시간에 있다면, 그는 그날 대학교에서 j - i + 1시간을 보낸다. 어떤 날에 수업이 없다면 Ivan은 집에 머물며, 따라서 대학교에서 0시간을 보낸다.

Ivan은 대학교에서 많은 시간을 보내는 것을 좋아하지 않으므로, 일부 수업을 빠지기로 했다. 그는 한 주 동안 k개보다 많은 수업을 빠질 수 없다. 어떤 수업을 빠지고 어떤 수업에 참석할지 정한 뒤, Ivan은 매일 자신이 빠지지 않는 첫 수업이 시작되기 직전에 대학교에 들어가고, 참석하기로 한 마지막 수업이 끝난 뒤 대학교를 떠난다. If Ivan가 어떤 날의 모든 수업을 빠지면, 그날은 대학교에 전혀 가지 않는다.

n, m, k와 Ivan의 시간표가 주어질 때, 그가 k개보다 많은 수업을 빠질 수 없다면 한 주 동안 대학교에서 보내야 하는 최소 시간을 구할 수 있는가?

첫째 줄에 세 정수 n, m, k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 500)가 주어진다. 각각 Berland의 한 주에 포함된 날의 수, 하루의 근무 시간 수, Ivan이 빠질 수 있는 수업의 수를 나타낸다.

이어서 n개의 줄이 주어지며, i-th번째 줄에는 m개의 문자로 이루어진 이진 문자열이 주어진다. i-th번째 줄의 j-th번째 문자가 1이면 Ivan은 i-th번째 날의 j-th번째 시간에 수업이 있다(0이면 그러한 수업이 없다).

Ivan이 k개보다 많은 수업을 빠지지 않을 때, 한 주 동안 대학교에서 보내야 하는 최소 시간을 출력한다.

첫 번째 예제에서 Ivan은 첫날의 두 수업 중 어느 것이든 빠질 수 있으므로, 첫날에는 1시간을 보내고 둘째 날에는 4시간을 보낸다.

두 번째 예제에서 Ivan은 어떤 수업도 빠질 수 없으므로, 매일 4시간을 보낸다.