Bracket Partitions

Time limit7sMemory limit1024 MB

Summary

Split a bracket string of length n into k contiguous parts so that the total number of correct bracket substrings across all parts is as small as possible.

Level: Hard8 of 10
Topics: Dynamic programming, Binary search, Prefix sum
Solved: No attempts yet

Problem

You have probably heard of bracket expressions before, but as a refresher, here is the definition:

() is a correct bracket expression.
If S is a correct bracket expression, then (S) is also a correct bracket expression.
If S1 and S2 are correct bracket expressions, then S1S2 is also a correct bracket expression.
No word that cannot be built with the rules above is a correct bracket expression.

The bracket value of a word made only of '(' and ')' is the number of its substrings that are correct bracket expressions. If the same substring occurs several times, each occurrence is counted.

You are given a word of length $n$ made only of '(' and ')'. The word does not have to be a correct bracket expression. Split it into $k$ non-empty intervals so that every character belongs to exactly one interval. Minimize the sum of the bracket values of the resulting words.

Input

The first line contains two integers $n$ and $k$ (1 ≤ k ≤ n ≤ 100 000), the length of the word and the number of intervals.

The second line contains the word of length $n$ , made only of '(' and ')'.

Output

Print one integer: the minimum possible sum of the bracket values of the $k$ words after an optimal split.

Examples2

Example 1
Input
```
15 2
())(()())()(())
```
Expected output
```
6
```
Example 2
Input
```
15 3
())(()())()(())
```
Expected output
```
3
```