P7315 [COCI 2018/2019 #3] Sajam

原时限 5s，这里设为 1s，经测试正确算法可以正常通过。 Milo 组织了一场圣诞游园会。结束后，他想通过 LEET 来实现熄灯。

每个区域都由 $N$ 行组成，其中每行有 $N$ 个摊位。现有 $3$ 种操作方式改变发光状态指将原来发光的灯改为熄灭，反之亦然）： 1. LEET 将选定一整行，并自动将这行所有的灯改变发光状态。 2. LEET 将选定一整列，并自动将这列所有的灯改变发光状态。 3. Milo 将选定一个摊位，并手动将该摊位的灯改变发光状态。 是否有方案使得 Milo 能在最多进行 $K$ 次操作 3 的情况下，将所有灯全部熄灭？

第一行输入整数 $N,K$。 接下来的 $N$ 行，每行有 $N$ 个字符 `x` 或 `o`，表示圣诞游园会对应摊位灯的发光状态。其中 `x` 指熄灭，`o` 指发光。

如果有符合题意的方案，则输出 `DA`，否则输出 `NE`。

#### 样例 3 解释 一种符合题意的方案： - 执行操作 $2$，选定第 $1$ 列。 - 执行操作 $3$，选定 $(2,2)$。 - 执行操作 $1$，选定第 $2$ 行。 - 执行操作 $2$，选定第 $4$ 列。 - 执行操作 $3$，选定 $(3,3)$。 #### 数据规模与规定 对于 $15$ 分的数据，$K=0$。 对于另外 $15$ 分的数据，$N \le 100$。 对于另外 $30$ 分的数据，$K \lt \dfrac{N}{2}$。 对于 $100\%$ 的数据，$1 \le N \le 1000$，$0 \le K \le N$。 #### 说明 **本题分值按 COCI 原题设置，满分 $90$。这里只选取其中具有梯度的 $18$ 个测试点进行评测。** **题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf) _T3 Sajam_。**