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

• 字符串 () 是一个合法的括号序列。
• 如果 $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

说明

在第一个样例中，一个最优的字符串划分方式如下：

())(()())()(()) 划分为 ())(()( 和 ))()(())。

第一个子串 ())(()( 包含 $2$ 个合法的括号序列：

• **()**)(()(
• ())(**()**(

第二个子串 ))()(()) 包含 $4$ 个合法的括号序列：

• ))**()**(())
• ))()(**()**)
• ))()**(())**
• ))**()(())**

因此，括号性之和为 $2 + 4 = 6$。

在第二个样例中，一个最优的字符串划分方式如下：

())(()())()(()) 划分为 ())((、)())()(( 和 ))。

子任务

• 在某些测试组中，满足 $n \le 18$。
• 在某些测试组中，满足 $n \le 300$。
• 在某些测试组中，满足 $n \le 4000$。
• 在某些测试组中，满足 $k \le 30$。

对于上述每个条件，都存在至少一个满足该条件的测试组。不同条件对应的测试组可能重叠，也可能不重叠。