Bracket Wheel

Time limit: 0.9s Memory limit: 512MB Input: Output:

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 nn parantheses, placed on a circular frame, that can be seen as a sequence of nn 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 a1,,ana_1, \dots , a_n, the sequence has nn cyclic shifts: n1n − 1 of form ai,,an,a1,,ai1a_i, \dots , a_n, a_1, \dots , a_{i−1} when 1<in1 < i ≤ n, and one cyclic shift equal to the original sequence a1,,ana_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 aa 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 ss, we define the value of ss, denoted by val(s)val(s), to be the number of cyclic shifts of ss that are balanced. For example, if s=s = ()(()), we have val(s)=2val(s) = 2, due to the cyclic shifts ()(()) and (())().

The rules of the game are simple. The player is given kk 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 ss is the sequence on the wheel, then the score is val(s)val(s). Can you help Seby spend his kk Gold Medals to maximise his score?

Formally, you are given a sequence ss of nn parentheses, and have the ability to swap kk pairs of parentheses within ss. 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 nn and kk. The second line of the input contains the sequence ss of parentheses.

Output data

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

Restrictions

  • 1n50 0001 ≤ n ≤ 50 \ 000
  • 1k91 ≤ k ≤ 9
  • ss contains only parentheses i.e. ( and ). It is guaranteed that the number of ( in ss 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.
# Points Restrictions
1 7 n500,k=0n \leq 500, k = 0
2 9 n20,k=1n \leq 20, k = 1
3 13 n500,k=1n \leq 500, k = 1
4 17 k=0k = 0
5 18 n2 000,k=1n \leq 2 \ 000, k = 1
6 19 k=1k = 1
7 17 No further restrictions.

Example

stdin

6 1
)(())(

stdout

3

Explanation

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

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

Out of these, only 33 are balanced sequences.

Log in or sign up to be able to send submissions!