Orchard

Time limit1sMemory limit128 MB

Summary

Given an n by n grid of trees and empty cells, decide whether the whole grid can be split into exactly k axis-aligned rectangles, each containing at least one tree.

Level: Medium7 of 10
Topics: Divide and conquer, Dynamic programming, Greedy, Implementation
Solved: No attempts yet

Problem

Old Bajtazar owns an orchard where the apple trees bear fruit of pure gold. The work is hard and he no longer has the strength he once had, so he decided to cut the orchard into parcels and hand them to his sons. He wants every son to live well, so each parcel has to hold at least one of the precious apple trees.

The orchard is a square with side $n$ meters. Put a coordinate system on it so that the lower left corner of the orchard is $(0, 0)$ and the upper right corner is $(n, n)$ . For every unit square we know whether an apple tree grows there. Each parcel has to be a rectangle whose four sides lie on grid lines. Parcels may not overlap, they may only touch along a side or at a corner, and together they have to cover the whole orchard with no gap. The size of a parcel does not matter. Every parcel only has to hold at least one apple tree.

Bajtazar has $k$ sons. Decide whether the orchard can be cut into exactly $k$ parcels under these rules.

Input

The first line contains the side length of the orchard $n$ and the number of sons $k$ ( $1 \le n \le 1000$ , $1 \le k \le n^2$ ).

Each of the next $n$ lines describes one row of unit squares and holds $n$ characters x and .. An x is a square with an apple tree, a . is a square without one.

Output

Print YES on the first line if the orchard can be cut into exactly $k$ parcels under these rules, and NO if it cannot.

Hint

The picture below shows the orchard of the first example cut into five parcels. An X marks a square with an apple tree.

Examples2

Example 1

Input

6 5
..x..x
..x...
....x.
xx.x.x
......
......

Expected output

YES

Example 2
Input
```
3 4
x.x
...
x.x
```
Expected output
```
YES
```