题目描述
花花和啾啾是好朋友。他们做完了切糕之后，打算一起切串。
一个括号串的权值是合法括号子串的数量。
现在他们有 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≤k≤n≤5×105，不保证给定括号串合法。
| 子任务编号 | n≤ | k≤ | 分数 |
|---|---|---|---|
| 1 | 300 | 5 | |
| 2 | 4000 | 10 | |
| 3 | 40000 | 10 | |
| 4 | 105 | 30 | 15 |
| 5 | 105 | 20 | |
| 6 | 3×105 | 20 | |
| 7 | 5×105 | 20 |