大家一定听说过括号序列，为了复习，我们先回顾一下它的定义：

• 字符串 () 是一个合法的括号序列。
• 如果 $S$ 是一个合法的括号序列，那么字符串 $(S)$ 也是一个合法的括号序列。
• 如果 $S_1$ 和 $S_2$ 是合法的括号序列，那么字符串 $S_1S_2$ 也是一个合法的括号序列。
• 任何不符合上述规则的字符串都不是合法的括号序列。

对于一个仅由字符 '(' 和 ')' 组成的字符串，我们将其“括号性”定义为该字符串中作为合法括号序列的子串的数量。在此定义下，每个子串出现的次数都要计入总数。

给定一个长度为 $n$、仅由 '(' 和 ')' 组成的字符串，以及一个整数 $k$。该字符串不一定是一个合法的括号序列。你的任务是将该字符串划分为 $k$ 个非空区间（每个字符必须恰好属于一个区间），使得划分后所有子串的括号性之和最小。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 100\,000$)，分别表示字符串的长度和我们要划分的区间数量。 第二行包含一个长度为 $n$ 的字符串，仅由 '(' 和 ')' 组成。

输出格式

输出一行一个整数，表示在最优划分下，划分出的 $k$ 个字符串的括号性之和的最小值。

样例

输入格式 1

15 2
())(()())()(())

输出格式 1

6

输入格式 2

15 3
())(()())()(())

输出格式 2

3