Ngoặc đúng

Bạn được cho một xâu \(s\) độ dài \(n\) chỉ gồm các ký tự ( hoặc ).
Ta gọi \(t_i\) là xâu xoay vòng thứ \(i\) của \(s\) \((0 \le i < n)\), với:
$
t_i = s_{i+1}s_{i+2}\ldots s_{n}\,s_{1}s_{2}\ldots s_{i}.
$

Ta biết rằng, một xâu ngoặc đúng thỏa các tính chất sau:

• Xâu rỗng là xâu ngoặc đúng.
• Nếu \(A\) là xâu ngoặc đúng, thì ( \(A\) ) cũng là xâu ngoặc đúng.
• Nếu \(A\) và \(B\) là hai xâu ngoặc đúng, thì \(AB\) cũng là xâu ngoặc đúng.

Gọi \(f(s)\) là số lượng các xâu \(t_i\) trong \(n\) xâu xoay vòng của \(s\) mà \(t_i\) là xâu ngoặc đúng.
Bạn được phép thực hiện đổi chỗ hai ký tự bất kỳ trong xâu \(s\) không quá \(k\) lần.
Hãy tìm cách đổi chỗ sao cho \(f(s)\) là lớn nhất.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(n, k\) (\(1 \le n \le 5 \times 10^4\), \(0 \le k \le 9\))--- độ dài xâu và số lần đổi chỗ tối đa.
• Dòng thứ hai chứa xâu \(s\) độ dài \(n\) gồm chỉ hai ký tự ( và ).
  Dữ liệu đảm bảo số lượng dấu ( và ) là bằng nhau.

\OutputFile

• In ra một số nguyên duy nhất là giá trị lớn nhất có thể của \(f(s)\).

\Scoring

• Subtask 1 (7 điểm): \(n \le 500\), \(k = 0\).
• Subtask 2 (9 điểm): \(n \le 20\), \(k = 1\).
• Subtask 3 (18 điểm): \(n \le 500\), \(k = 1\).
• Subtask 4 (14 điểm): \(k = 0\).
• Subtask 5 (16 điểm): \(n \le 2000\), \(k = 1\).
• Subtask 6 (19 điểm): \(k = 1\).
• Subtask 7 (17 điểm): Không có ràng buộc bổ sung.

Example

4 1
(())

2

6 0
(())()

2