West Lake Tower Partition

Sun Yixie is planning to open a restaurant by building a West Lake Elegant Gathering place using various parts. He has n parts, where each part is represented as an h × w binary matrix. Each element of the matrix is either 0 or 1. The area of part i is defined as:

[ S(i)=\sum_{r=1}^{h}\sum_{c=1}^{w}a_{r,c} ]

For two parts represented by matrices a and b (with indices l and r respectively), define their stability score as:

[ f(l,r)=\sum_{r=1}^{h}\sum_{c=1}^{w} \Bigl[\bigl(a_{r,c}=1\bigr) \text{ and } \bigl(b_{r,c}=1\bigr)\Bigr] ]

Sun Yixie will split the parts into two groups. One group (the big tower) will be arranged in any order using some of the parts, while the remaining parts will form the small tower. It is allowed to have no small tower if all parts are used for the big tower.

For any tower having a set U of part indices, the tower is considered to be successfully built if and only if for every two parts i and j in U the following condition holds:

[ \forall i,j\in U,\quad f(i,j)\ge \left\lceil\frac{\min(S(i),S(j))}{2}\right\rceil. ]

Your task is to choose a partition of the parts into two groups (big and small towers) such that both towers (if non-empty) satisfy the above condition and the big tower uses as many parts as possible. If it is impossible to build both towers successfully, output -1. Otherwise, output the maximum number of parts that can be used in the big tower.

inputFormat

The first line contains three integers n, h, and w — the number of parts, and the dimensions of each part.

Then, for each part from 1 to n, there are h lines, each containing a binary string of length w representing the part.

outputFormat

Output a single integer: the maximum number of parts that can be used in the big tower under the given conditions. If it is impossible to build both towers successfully, output -1.

sample

3 2 2
11
10
11
11
01
01

3