infO(1) Cup 2024 Mirror - Day 2 | Bracket Wheel

Money Gold Medals can’t buy happiness ~ Certainly not a programmer

Seby the little square has recently heard about the newest attraction in the Info(1)cup Fair: the bracket wheel! The wheel consists of $n$ parantheses, placed on a circular frame, that can be seen as a sequence of $n$ characters, each of which can either be ( or ). Spinning the wheel is equivalent to transforming it into one of its cyclic shifts.

Now, we define the cyclic shifts of a sequence as follows. Given a sequence $a_1, \dots , a_n$, the sequence has $n$ cyclic shifts: $n − 1$ of form $a_i, \dots , a_n, a_1, \dots , a_{i−1}$ when $1 < i ≤ n$, and one cyclic shift equal to the original sequence $a_1, \dots , a_n$. For example the sequence of parentheses ()(()) has the following cyclic shifts:

1. ()(())
2. )(())(
3. (())()
4. ())()(
5. ))()((
6. )()(()

We call a sequence of parentheses balanced if we can insert 1 and + into the sequence so that it becomes a valid mathematical expression. For example, (())() is balanced, since we can insert 1 and + to form ((1 + 1) + 1) + (1 + 1), but )(() or (() are not. More formally, a sequence $a$ is balanced if and only if it is empty or of the form (b)c where b and c are balanced.

Task

Given a sequence of parentheses $s$, we define the value of $s$, denoted by $val(s)$, to be the number of cyclic shifts of $s$ that are balanced. For example, if $s =$ ()(()), we have $val(s) = 2$, due to the cyclic shifts ()(()) and (())().

The rules of the game are simple. The player is given $k$ Gold Medals. They can spend one gold medal to swap two parentheses on the wheel. The score of the player is then the number of cyclic shifts of the sequence on the wheel which are balanced. That is, if $s$ is the sequence on the wheel, then the score is $val(s)$. Can you help Seby spend his $k$ Gold Medals to maximise his score?

Formally, you are given a sequence $s$ of $n$ parentheses, and have the ability to swap $k$ pairs of parentheses within $s$. Find a way to perform these swaps in order to maximize the value of the resulting sequence.

Input data

The first line of the input contains the integers $n$ and $k$. The second line of the input contains the sequence $s$ of parentheses.

Output data

The output contains the maximum value that could be obtained after performing the swaps.

Restrictions

• $1 ≤ n ≤ 50 \ 000$
• $1 ≤ k ≤ 9$
• $s$ contains only parentheses i.e. ( and ). It is guaranteed that the number of ( in $s$ is equal to the number of ).
• The number of Gold Medals Seby won is significantly bigger, but his instinct tells him he might need them again in the near future.

Example

stdin

6 1
)(())(

stdout

3

Explanation

In this case, we can swap parantheses on positions $3$ and $4$. The resulting sequence is )()()(, which has the following cyclic shifts:

1. )()()(
2. ()()()
3. )()()(
4. ()()()
5. )()()(
6. ()()()

Out of these, only $3$ are balanced sequences.