题目描述
花花和啾啾是好朋友。他们做完了切糕之后，打算一起切串。
一个括号串的权值是合法括号子串的数量。
现在他们有 $k$ 要把一个长度为 $n$ 的括号串 $S$ 切成 $k$ 个部分。他们组成了原串的划分。而划分方案的权值为每个部分的括号串权值之和。
花花和啾啾想知道，划分权值最小的方案的权值是多少呢？
输入格式
第一行输入两个正整数 $n,k$。 第二行输入一个长度为 $n$ 的括号串 $S$。
输出格式
一个整数即为答案。
样例
样例输入1
8 2
()(()(()样例输出1
2样例输入2
14 3
(()(((((())))(样例输出2
0样例输入3
24 3
()()((()))()()()(()((())样例输出3
8样例 4/5 在下发文件中。
数据范围
$1\le k \le n \le 5\times 10^5$，不保证给定括号串合法。
| 子任务编号 | $n \le$ | $k\le$ | 分数 |
|---|---|---|---|
| 1 | $300$ | 5 | |
| 2 | $4000$ | 10 | |
| 3 | $40000$ | 10 | |
| 4 | $10^5$ | $30$ | 15 |
| 5 | $10^5$ | 20 | |
| 6 | $3\times 10^5$ | 20 | |
| 7 | $5\times 10^5$ | 20 |