A-好哥哥_牛客小白月赛36

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一段合法括号序列和 $n$ 元钱，合法括号序列的定义如下：

1. $()$ 是合法的括号序列。

2.若字符串 $A$ 是合法的括号序列，那么 $(A)$ 也是合法的括号序列。

3.若字符串 $A$ , $B$ 是合法的括号序列，那么 $AB$ 也是合法的括号序列。

我们设定 $G_{x}$ 表示第 $x$ 对括号的层数，即：它前面有多少未匹配的左括号。同时规定一对括号 $A$ 是另一对括号 $B$ 的好哥哥，当且仅当 $G_{A}=G_{B}+1$ 且括号 $A$ 在括号 $B$ 内。

如果当前位于一对括号 $Q$ ，每次可以花费 $1$ 元跳到：

1. 它的任意一个好哥哥。

2. 一对括号 $X$ ，要求 $X$ 的好哥哥是 $Q$ 。

假如一开始位于第一对括号，请问最多可以经过多少对不重复的括号？

第一行两个正整数 $v$ , $n$ ， $v$ 表示括号对数， $n$ 表示钱的数量，其中 $v\leq 10^{7}$ , $n\leq 10^{7}$ 。

接下来一行输入长度为 $2 \times v$ 的括号序列。

输出最多可以经过多少对不重复的括号。

示例1

复制

5 2
((((()))))

复制

示例2

复制

9 5
((()(()()))(()()))

复制