Maximum Dance Songs

At a ball, there are (n) boys and (n) girls. At the beginning of every dance, all boys and girls are paired into exactly (n) couples for a waltz such that no boy dances with the same girl in more than one dance. Some boys and girls mutually like each other, while others do not (there is no one‐way affection). Each boy is willing to dance with at most (k) girls he does not like, and each girl is willing to dance with at most (k) boys she does not like. Given the mutual liking information for every pair, determine the maximum number of dances that can be held.\n\nA valid dance schedule is a sequence of disjoint perfect matchings (each matching is a pairing between all boys and girls) such that for every participant, the number of dances in which they dance with someone they do not like does not exceed (k). Since each participant dances in every dance, if a person dances in (D) dances, then they must dance with at least (D - k) partners they like. Note that every liked pair (if used in a dance) can only be used once, and overall the total number of liked pairs available is limited.\n\nA necessary and sufficient condition to have a valid schedule with (D) dances is that:\ ( \begin{aligned} D &\le n,\ D &\le k + L_i \quad \text{for every boy } i,\ D &\le k + L'j \quad \text{for every girl } j,\ D &\le k + \left\lfloor \frac{L{total}}{n} \right\rfloor, \end{aligned} ) where (L_i) is the number of girls that boy (i) likes, (L'j) is the number of boys that girl (j) likes, and (L{total}) is the total number of liked pairs. Therefore, the answer is given by (D = \min\Bigl(n,;k+\min_{i}(L_i),;k+\min_{j}(L'j),;k+\Bigl\lfloor\frac{L{total}}{n}\Bigr\rfloor\Bigr)).

inputFormat

The first line contains two integers (n) and (k) (1,(\le n \le) 10⁵, 0 (\le k \le n)), representing the number of boys (and girls) and the maximum number of dances with a disliked partner permitted for each person. The following (n) lines each contain (n) integers. The (j^{th}) integer in the (i^{th}) line is either 1 or 0, indicating whether boy (i) and girl (j) like each other (1 means they like each other, and 0 means they do not). It is guaranteed that the liking relationship is mutual.

outputFormat

Output a single integer representing the maximum number of dances that can be held under the given constraints.

sample

3 1
1 0 0
0 1 0
0 0 1

2