### Problem Statement

Jack has bought a rectangular table containing a grid of lamps. Each lamp is initially either "on" or "off". There is a switch underneath each column, and when the switch is flipped, all the lamps in that column reverse their states ("on" lamps become "off" and vice versa).

A row in the grid is considered lit if all the lamps in that row are "on". Jack must make exactly K flips. The K flips do not necessarily have to be performed on K distinct switches. His goal is to have as many lit rows as possible after making those flips.

You are given a String[] initial, where the j-th character of the i-th element is '1' (one) if the lamp in row i, column j is initially "on", and '0' (zero) otherwise. Return the maximal number of rows that can be lit after performing exactly K flips.

### Definition

 Class: LampsGrid Method: mostLit Parameters: String[], int Returns: int Method signature: int mostLit(String[] initial, int K) (be sure your method is public)

### Constraints

-initial will contain between 1 and 50 elements, inclusive.
-Each element of initial will contain between 1 and 50 characters, inclusive.
-Each element of initial will contain the same number of characters.
-Each element of initial will contain only the digits '0' and '1'.
-K will be between 0 and 1000, inclusive.

### Examples

0)

 ```{"01", "10", "10"}``` `1`
`Returns: 2`
 Here, Jack must flip exactly one switch. If he flips the switch for the second column, the bottom two rows become lit.
1)

 `{"101010"}` `2`
`Returns: 0`
2)

 `{"00", "11"}` `999`
`Returns: 0`
 No row can be lit after exactly 999 flips.
3)

 ```{"0", "1", "0", "1", "0"} ``` `1000`
`Returns: 2`
4)

 `{"001", "101", "001", "000", "111", "001", "101", "111", "110", "000", "111", "010", "110", "001"}` `6`
`Returns: 4`
5)

 `{"01", "10", "01", "01", "10"}` `1`
`Returns: 3`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10154

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13694&pm=10154

nika

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

Search