Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3675
Trim the Nails

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Robert is clipping his fingernails. But the nail clipper is old and the edge of the nail clipper is potholed.

The nail clipper's edge is N millimeters wide. And we use N characters('.' or '*') to represent the potholed nail clipper. '.' represents 1 bad millimeter edge, and '*' represents 1 good millimeter edge.(eg. "*****" is a 5 millimeters nail clipper with the whole edge good. "***..." is a 6 millimeters nail clipper with half of its edge good and half of its edge bad.)

Notice Robert can turn over the clipper. Turning over a "**...*"-nail clipper will make a "*...**"-nail clipper.

One-millimeter good edge will cut down Robert's one-millimeter fingernail. But bad one will not. It will keep the one-millimeter unclipped.

Robert's fingernail is M millimeters wide. How many times at least should Robert cut his fingernail?

#### Input

There will be multiple test cases(about 15). Please process to the end of input.

First line contains one integer N.(1≤N≤10)

Second line contains N characters only consists of '.' and '*'.

Third line contains one integer M.(1≤M≤20)

#### Output

One line for each case containing only one integer which is the least number of cuts. If Robert cannot clipper his fingernail then output -1.

```8
****..**
4
6
*..***
7
```

```1
2
```

#### Hint

```We use '-' to present the fingernail.
For sample 1:
fingernail:	----
nail clipper:	****..**
Requires one cut.

For sample 2:
fingernail:			-------
nail clipper:			*..***
nail clipper turned over:	 ***..*
Requires two cuts.
```

Author: YANG, Jueji
Contest: ZOJ Monthly, November 2012
Submit    Status