P9266 [PA 2022] Bracket Partitions

**This problem is translated from [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Round 5 [Nawiasowe podziały](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/naw/).** 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.

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 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.

For $100\%$ of the testdata, it holds that: $1\le k\le n\le 10 ^ 5$。 Translated by ChatGPT 5