Raehwan enjoys writing down his emotions in a notebook at the end of each day. If his overall emotion that day was happy, he writes :), and if not, he writes :(.

As he continued to write down his emotions for $N$ days, he began to run out of space in his notebook and felt the need to compress and organize his previous records. Raehwan decided that if the emotions for consecutive days were the same, he would write the number of consecutive days after :) or :(. For example, :):):) would be written as :)3, and :(:(:):) would be written as :(2:)2. However, if the emotion lasted for only one day, he would not write a 1 after :) or :( and just write :) or :(. Therefore, :):(:(:):) would be written as :):((2:)2.

However, due to the overwhelming number of records, Raehwan wants to minimize the length of the organized string by flipping $0$ to $K$ emotions. Flipping :) changes it to :((, and flipping :(( changes it to :). At the same time, he wants to maintain the overall flow of emotions, so the number of :) and :(( must remain unchanged after flipping.

Write a program to determine how Raehwan can neatly organize his emotional records.

Input

The first line contains a string $S$ of length $2N$ representing the emotion records.

The second line contains an integer $K$.

Output

Output the minimum length of the string that can be created when the emotion record $S$ is compressed and organized.

Constraints

• $1 \le N \le 75$
• $S_{2i - 1} = $ \texttt{:}, $S_{2i} \in \{ $ \texttt{)}, \texttt{(} $\} (1 \le i \le N)$
• $0 \le K \le N$

Scoring

Examples

Input 1

:):):(:):(
2

Output 1

6

Input 2

:(:):):(:(
0

Output 2

8

Input 3

:):):):):):):):):):):):)
6

Output 3

4

Note

In Example 1, by flipping the 3rd and 4th emotions in :):):(:)(, it becomes :):):):((, which can be compressed to :)3:(2.

In Example 2, :((:):)(:( is compressed to :((:)2:(2.

In Example 3, :):):):):):):):):):):) is compressed to :)12, and it is impossible to compress it shorter by flipping the emotions.