题目描述

给定 $n$ 个连成一串的符号。符号只可能是 + 或者是 -。我们需要将这些符号划分成几个区间段落。每一段至少一个符号，至多 $d$ 个符号（$d$ 为一个给定的整数）。

在一个段落中，若减号数量大于或等于加号，则称这个段落是负能量的；否则，就是正能量的。

请问如何划分，才能让负能量的段落达到最少，输出这个最少值。

输入格式

• 第一行：两个整数表示 $n$ 与 $d$
• 第二行：$n$ 个符号，以$s_1s_2\dots s_n$表示

输出格式

• 单个整数：表示答案。

10 3
---+-++-++

1

样例解释 1

{---}{+-+}{+-+}{+}

数据范围

• 对于 $30\%$ 的数据，$1\leq d \leq n\leq 20$
• 对于 $60\%$ 的数据，$1\leq d \leq n\leq 5,000$
• 对于 $100\%$ 的数据，$1\leq d \leq n\leq 300,000$