Toggle Grid Lights

We are given an N×N grid, where each cell represents a light booth. Each light has a state: on (represented by 1) or off (represented by 0). There are three types of operations that can flip (i.e. change) the state of a light (from on to off, or off to on):

1. Operation 1: LEET selects an entire row and automatically flips the state of every light in that row.
2. Operation 2: LEET selects an entire column and automatically flips the state of every light in that column.
3. Operation 3: Milo selects an individual booth and manually flips the light state. However, Milo is allowed to use this operation at most K times.

The operations are applied in any order, and note that flipping is its own inverse (i.e. performing the same flip twice returns the light to its original state). In other words, the final state of a cell (i, j) is given by:

\( \text{final}_{ij} = A_{ij} \oplus r_i \oplus c_j \oplus m_{ij} \),

where:

• A_ij is the initial state (0 or 1) of the cell,
• r_i is 1 if row i is flipped (operation 1), 0 otherwise,
• c_j is 1 if column j is flipped (operation 2), 0 otherwise,
• m_ij is 1 if the cell (i, j) is manually flipped (operation 3), and manually flipping is allowed for at most K cells in total.

The goal is to decide whether there exists a sequence of operations (with an arbitrary number of row and column flips, and at most K manual flips) such that all lights become off (i.e. final state is 0 for every cell).

Hint: Since the operations are independent and commutative, you can choose the row flips r and column flips c arbitrarily, and then for each cell the manual flip m is forced: \(m_{ij} = A_{ij} \oplus r_i \oplus c_j\). The total number of manual operations is thus the sum over all cells. With a fixed choice for r, you can optimize the choice for each column by selecting c[j] to minimize the manual operations required in that column.

inputFormat

The first line contains two integers N and K (1 ≤ N ≤ 10, 0 ≤ K ≤ N*N), where N is the dimension of the square grid and K is the maximum number of allowed manual flips.

Then follow N lines, each containing a string of length N consisting of characters '0' and '1'. The character '1' indicates that the light is initially on, and '0' indicates off.

outputFormat

Output a single line: YES if there exists a sequence of operations such that all lights can be turned off using at most K manual flips; otherwise, output NO.

sample

2 1
00
00

YES