Orchard

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.

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.

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

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