Problem Description

This problem is translated from PA 2022 Round 5 Nawiasowe podziały.

I am sure you know bracket sequences, but just in case, and as a review, let us recall their definition:

• () is a valid bracket sequence.
• If $S$ is a valid bracket sequence, then (S) is also a valid bracket sequence.
• If both $S_1$ and $S_2$ are valid bracket sequences, then $S_1S_2$ is also a valid bracket sequence.
• Any bracket sequence that does not satisfy the rules above is not a valid bracket sequence.

You are given a string of length $n$ consisting only of the characters ( and ), and a number $k$. The string is not necessarily a valid bracket sequence. Your task is to split it into $k$ non-empty segments (each character must belong to exactly one segment), so that the sum, over all segments, of the number of substrings that are valid bracket sequences is minimized.

Input Format

The first line contains two integers $n, k$, representing the length of the string and the number of segments to split into.

The second line contains a string of length $n$, guaranteed to consist only of ( and ).

Output Format

Output one integer in a single line, the minimum possible value of the sum, over all segments, of the number of substrings that are valid bracket sequences.

15 2
())(()())()(())

6

15 3
())(()())()(())

3

Hint

For $100\%$ of the testdata, it holds that:

$1\le k\le n\le 10 ^ 5$。

Translated by ChatGPT 5