Background

This problem is translated from POI2022~2023R1 ply.

Problem Description

Define a "valid bracket sequence" and its depth as follows:

• The empty string is a valid bracket sequence, with depth $0$.
• If $w$ is a valid bracket sequence with depth $h$, then $(w)$ is also a valid bracket sequence with depth $h+1$.
• If $w_1$ and $w_2$ are both valid bracket sequences with depths $h_1$ and $h_2$, then $w_1w_2$ is also a valid bracket sequence, with depth $\max(h_1,h_2)$.

Define flipping a character as:

• If the current character is (, change it to ).
• If the current character is ), change it to (.

You need to flip some characters in $s$ so that the depth does not exceed $H$. Find the minimum number of operations.

Input Format

The first line contains two integers $n \ (2 \leq n \leq 10^6)$ and $H \ (1 \leq H \leq \frac{n}{2})$, representing $|s|$ and the required maximum depth after modification.

The second line contains a string $s$, representing the original bracket sequence.

Output Format

Output the minimum number of modifications.

8 2
(()(()))

2

Hint

For the sample, you can modify it to (()()()), whose depth is $2$.

The subtasks are as follows:

Note: $h$ is the depth of the input bracket sequence.

In this problem, subtask $0$ is the sample.

Translated by ChatGPT 5