Richard Roe 刚刚实现了一个全新的数据结构 $S$。它只能执行两种操作：“add” 和 “query”。

• “add” 向 $S$ 中添加一个元素。你可以假设该操作耗时为零。
• “query” 向 $S$ 发起一次请求。该操作耗时 $x$ 秒，其中 $x$ 等于之前添加的元素数量。

关于这些操作的其他细节对于本题并不重要。

Richard 突然意识到，他可以通过不时地重建（rebuild）该结构来优化它。于是他实现了一个名为 “rebuild” 的新函数。这个新函数的工作方式如下：当调用 “rebuild” 时，$S$ 会“忘记”重建之前添加的元素。更准确地说，在添加此操作后：

• “add” 向 $S$ 中添加一个元素，耗时为零。
• “query” 向 $S$ 发起一次请求，耗时 $x$ 秒，其中 $x$ 等于自上次调用 “rebuild” 以来添加的元素数量（此处假设在所有查询之前也调用了一次 “rebuild”）。
• “rebuild” 耗时 $y$ 秒。

给定一个包含 “add” 和 “query” 操作的序列。你的任务是在某些位置插入 “rebuild” 操作，使得所有操作的总耗时最小。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $y$ ($1 \le n \le 10^6$, $0 \le y \le 10^6$)。

第二行包含一个长度为 $n$ 的字符串 $q$。$q$ 中的每个字符要么是 “+”，要么是 “?”（不含引号）。其中，“+” 表示一次 “add” 调用，“?” 表示一次 “query” 调用。这些操作按照 $q$ 中的顺序执行。

输出格式

输出一个整数 $t$：在可能添加若干次 “rebuild” 调用后，$S$ 处理所有查询所需的最小总时间（以秒为单位）。

样例

输入 1

6 5
++??+?

输出 1

6

输入 2

6 8
++??+?

输出 2

7

输入 3

5 1
+++++

输出 3

0

说明

在第一个样例中，最优的方法是在第一个 “?” 之前放置 “rebuild”。

在第二个样例中，放置任何 “rebuild” 操作都无法减少总时间。

在第三个样例中，由于根本没有 “query” 操作，因此也无法减少总时间。