Problema D - A floresta de Baguim

A grande floresta de Baguim do Monte é conhecida pela beleza natural das várias árvores que contém. O mapa da floresta é uma grelha de N unidades por N unidades em que em cada célula ou existe uma árvore ou um espaço vazio. Representamos cada árvore por um carácter '#' e cada espaço vazio por um '.'. Um exemplo de uma tal grelha, para N = 4 é o seguinte:

...#
.#..
...#
..#.

Este exemplo tem 4 árvores e 12 espaços vazios. O Alberto é um assíduo visitante da floresta e como tal pretende instalar um banco para ele e os seus amigos se sentarem. O grupo de amigos do Alberto é constituido por K pessoas (incluindo o Alberto) e por isso o Alberto quer construir um banco com K lugares. Este banco terá de ser constituido por um conjunto contíguo de K células horizontais desobstruídas (sem árvores) da grelha que representa a floresta, ou seja, terá de estar em K células com espaços vazios seguidas numa única linha. Por exemplo, se a floresta fosse a dada anteriormente e o grupo tivesse K = 3 pessoas, o Alberto poderia construir o seguinte banco (representado por caracteres '*') na primeira linha da floresta:

***#
.#..
...#
..#.

Infelizmente, nem sempre é possível construir um banco assim, se o grupo tivesse K = 4 pessoas, seria impossível construir um banco como descrito para a grelha acima. Dados os valores de N e K assim como a descrição da grelha da floresta, consegues determinar se é possível construir um banco para o número de amigos indicado (indicado pelo número 1 no output) ou não (indicado pelo número 0 no output)?

O Problema

Dada descrição da floresta de Baguim de tamanho N por N e um tamanho K do banco a construir nela, determinar se esta construção e possível.

Input

A primeira linha contém dois inteiros N e K, o tamanho da floresta e o tamanho do banco, respetivamente. As N linhas seguinte têm cada uma N caracteres que podem ser um '.' ou um '#', que definem a floresta como descrito.

Output

Um 0 ou um 1 consoante é possível ou não construir o banco.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Input do Exemplo 1

4 3
...#
.#..
...#
..#.

Output do Exemplo 1

1

Input do Exemplo 2

4 4
...#
.#..
...#
..#.

Output do Exemplo 2

0