Problem G
Veggja Kalli
Languages
en
is
Kalli is quite the carpenter and has a particular penchant for walls. Today Kalli received a new project. An apartment is being built, the plans for which are given by $N$ elements. Each element denotes a cell which is either a wall, denoted by #, or an open space, denoted by .. The leftmost and rightmost cells are always walls.
Kalli was asked to break the minimum amount of walls such that there would be a room of size exactly $M$. That is to say that there are exactly $M$ open cells side by side, neither less than or more than $M$. Kalli is not allowed to break the leftmost or rightmost walls since then the apartment is open to the elements.
Input
The first line of the input contains two integers $N$ and $M$ ($1 \leq M \leq N \leq 5\cdot 10^5$), the number of cells and the size of the room Kalli should make.
The next line contains a string with $N$ letters describing the apartment.
Output
A single line containing the minimum number of walls Kalli needs to break to satisfy the requirements should be printed. If no such number exists the program should instead print Neibb.
Scoring
|
Group |
Points |
Constraints |
|
1 |
28 |
$N \leq 100$ |
|
2 |
32 |
$N \leq 3\, 000$ |
|
3 |
40 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
7 2 #-#-#-# |
Neibb |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 3 #-###--# |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 3 #--# |
Neibb |
