Problem Description

Milo organized a Christmas fair. After it ended, he wants to turn off all the lights using LEET.

Each area consists of $N$ rows, with each row containing $N$ stalls. There are three ways to change the lighting status (i.e., turn on lights off and vice versa):

1. LEET selects an entire row and automatically changes the status of all lights in that row.
2. LEET selects an entire column and automatically changes the status of all lights in that column.
3. Milo selects a specific stall and manually changes the status of the light in that stall.

Is there a way for Milo to turn off all the lights with at most $K$ operations of type 3?

Input Format

The first line contains two integers $N$ and $K$.

The next $N$ lines each contain $N$ characters, either x or o, representing the lighting status of the corresponding stall at the Christmas fair. x means the light is off, and o means the light is on.

Output Format

If there is a solution that meets the criteria, output DA. Otherwise, output NE.

Sample Input and Output

Sample Input #1

2 0
ox
ox

Sample Output #1

DA

Sample Input #2

3 1
ooo
xoo
oox

Sample Output #2

NE

Sample Input #3

4 2
oxxo
xxox
oxoo
oxxo

Sample Output #3

DA

Notes

Sample 3 Explanation

One possible solution:

• Perform operation 2, select the first column.
• Perform operation 3, select $(2,2)$.
• Perform operation 1, select the second row.
• Perform operation 2, select the fourth column.
• Perform operation 3, select $(3,3)$.

Data Size and Constraints

For 15 points, $K=0$.

For another 15 points, $N \le 100$.

For another 30 points, $K < \dfrac{N}{2}$.

For 100% of the data, $1 \le N \le 1000$, $0 \le K \le N$.

Notes

This problem's score is set according to the original COCI contest, with a full score of 90. Here, only 18 test cases with varying difficulties are used for evaluation.

The problem is translated from COCI2018-2019 CONTEST #3 T3 Sajam.

见题面 Input 部分

见题面 Output 部分