시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB200393121.233%

문제

Fall Out Boy의 Dance, Dance라는 노래를 제일 좋아하는 세준이는 댄스 파티를 계획중이다. 이 댄스 파티에는 N명의 남자와 N명의 여자가 참석할 예정이다. 댄스 파티는 몇 개의 라운드로 진행될 예정이다.

각각의 라운드에서 세준이는 2N명의 손님을 N명의 쌍으로 나누려고 한다. 모든 손님은 하나의 쌍에 속해야 하고, 각 쌍에는 남자 1명과, 여자 1명이 있어야 한다.

모든 남자들은 모든 라운드에서 다른 여자와 춤을 춰야 한다. 어떤 남자와 어떤 여자는 서로 좋아하거나 서로 싫어한다. 하지만, 댄스 파티 동안, 모든 남자들은 많아야 K번은 자기가 싫어하는 여자와 춤을 출 수 있다고 했다. 비슷하게, 여자도 많아야 K번은 자기가 싫어하는 남자와 춤을 출 수 있다.

각각의 남자와 여자가 서로 좋아하는지 아닌지 정보가 주어졌을 때, 최대 몇 라운드 까지 갈 수 있는 지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 남자의 수 N과, K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 0보다 크거나 같고 50보다 작거나 같은 자연수이다. 둘째 줄에는 첫 번째 남학생과 첫 번째 여학생이 서로 좋아하면 1, 아니면 0이 주어지고, 두 번째 여학생도 주어지고, N 번째 여학생도 주어진다. 셋째 줄에는 두 번째 남학생,,,, 과 같이 주어진다.

출력

첫째 줄에 최대 몇 라운드까지 갈 수 있는지 출력한다.

예제 입력 1

3 0
111
110
101

예제 출력 1

2

예제 입력 2

3 0
111
111
111

예제 출력 2

3

예제 입력 3

2 0
10
10

예제 출력 3

0

예제 입력 4

2 1
10
10

예제 출력 4

1

출처