B - 直線塗り Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

イカの高橋君は床を塗るのが大好きです。床は N 個のマスが左右に 1 列に並んでいるような形をしています。左から i 個目のマスをマス i と呼ぶことにします。すでにいくつかのマスは塗られていますが、いくつかのマスは塗られていません。高橋君はインクを発射できる射程が R の銃を使って全てのマスを塗ろうとしています。高橋君は最初マス 1 にいます。そして、1 秒の間に以下のいずれか 1 つの行動が行えます。

  • 1 つ右のマスに移動する。すなわち、マス i からマス i+1 に移動する。ただし、マス N にいるときは行えない。
  • 銃を撃って床を塗る。マス i にいるときに銃を撃つと、マス i からマス i+R-1 までのマスを全て塗ることができる。ただし、i+R-1 が N より大きい場合は、マス i からマス N までのマスが塗られる。

高橋君が全てのマスを塗るためにかかる時間の最小値を求めてください。

入力

入力はイカの形式で標準入力から与えられる。

N R
S
  • 1 行目には、マス目の個数を表す整数 N (1 ≦ N ≦ 100) と銃の射程を表す整数 R (1 ≦ R ≦ N) が空白区切りで与えられる。
  • 2 行目には、長さ N の文字列 S が与えられる。このうち i (1 ≦ i ≦ N) 文字目は、マス i の情報を以下のように表す。
    • . の場合：このマスがまだ塗られていないことを表す。
    • o の場合：このマスがすでに塗られていることを表す。

出力

高橋君が全てのマスを塗るためにかかる時間の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

7 3
...o.o.

出力例1

6

銃を撃つ → 4 歩前進 → 銃を撃つ、という行動をとると時間が最小となります。

入力例2

8 4
...o.ooo

出力例2

3

銃を撃つ → 1 歩前進 → 銃を撃つ、という行動をとると時間が最小となります。

入力例3

4 4
oooo

出力例3

0

最初から全てのマスが塗られています。