Dance, Dance
시간 제한2초메모리 제한128 MB
남녀 N명씩을 짝지어 여러 라운드를 진행할 때, 같은 짝은 한 번만 만나고 각자 싫어하는 상대와는 최대 K번만 만나도록 하는 최대 라운드 수를 구합니다.
문제
Fall Out Boy의 노래 "Dance, Dance"를 가장 좋아하는 세준이는 댄스 파티를 계획하고 있다. 이 파티에는 남자 N명과 여자 N명이 참석하며, 파티는 여러 라운드로 진행된다.
각 라운드마다 세준이는 2N명의 손님을 N개의 쌍으로 나눈다. 모든 손님은 정확히 하나의 쌍에 속해야 하며, 각 쌍은 남자 1명과 여자 1명으로 이루어진다.
같은 남자와 여자가 두 번 이상 함께 춤출 수는 없다. 또한 어떤 남자와 어떤 여자는 서로 좋아하거나 서로 싫어한다. 파티 전체를 통틀어 각 남자는 자신이 싫어하는 여자와 많아야 K번만 춤출 수 있고, 각 여자도 자신이 싫어하는 남자와 많아야 K번만 춤출 수 있다.
각 남자와 여자가 서로 좋아하는지에 대한 정보가 주어질 때, 진행할 수 있는 라운드 수의 최댓값을 구하시오.
입력
첫째 줄에 남자의 수 N과 정수 K가 주어진다. N은 50 이하의 자연수이고, K는 0 이상 50 이하의 정수이다.
다음 N개의 줄에는 각 남자가 여자들을 좋아하는지 여부가 주어진다. i번째 줄은 길이 N의 0과 1로 이루어진 문자열이며, j번째 문자가 1이면 i번째 남자와 j번째 여자가 서로 좋아한다는 뜻이고, 0이면 서로 싫어한다는 뜻이다.
출력
진행할 수 있는 라운드 수의 최댓값을 출력한다.