Bracket Sequence Partitioning

This problem is adapted from [PA 2022 Round 5](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) "Nawiasowe podziały".

Recall the definition of a valid bracket sequence:

• () is a valid bracket sequence.
• If S is a valid bracket sequence then (S) is also valid.
• If S₁ and S₂ are valid bracket sequences then their concatenation S1S2 is valid.
• Any sequence that does not follow the above rules is invalid.

You are given a string S of length n consisting only of the characters ( and ), and an integer k. Note that S itself is not necessarily a valid bracket sequence. Your task is to partition S into k non-empty contiguous segments (each character must belong to exactly one segment) such that the total number of substrings that are valid bracket sequences in all segments is minimized.

A substring of a segment is any contiguous subsequence of that segment. For each segment, count all substrings that form a valid bracket sequence, and then sum these counts over all segments. You are to compute the minimum possible total sum.

For example, consider the string ()() partitioned into two segments () and (). Each segment has exactly one valid substring (()), so the answer is 2.

Note on Validity: A substring is valid if, when read from left to right, the number of ( is always not less than the number of ) and the total count of ( equals that of ) at the end.

All formulas below are in LaTeX format.

In particular, the recursive definition of a valid bracket sequence is:

$$\text{Base: } () \text{ is valid.}$$ $$\text{If } S \text{ is valid, then } (S) \text{ is valid.} $$$$\text{If } S_1 \text{ and } S_2 \text{ are valid, then } S_1S_2 \text{ is valid.} $$

inputFormat

The first line of input contains two integers n and k ($1 \le k \le n$), where n is the length of the string and k is the number of segments to partition into.

The second line contains a string S of length n consisting only of the characters ( and ).

outputFormat

Output a single integer representing the minimum total number of valid bracket sequence substrings over all k segments.

sample

2 1
()

1