← 返回题目列表

AtCoder · arc040_b

B. 直线绘画

中文机器翻译题面 查看原题

問題文

鱿鱼高桥喜欢粉刷地板。地板是 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

所有方块都是从头开始绘制的。