Dãy ngoặc đúng được định nghĩa như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng có bậc bằng ~0~.
• Nếu ~A~ là biểu thức ngoặc đúng có bậc bằng ~k~ thì ~(A)~, ~[A]~, ~\{A\}~ cũng là biểu thức ngoặc đúng có bậc ~k + 1~.
• Nếu ~A~ và ~B~ tương ứng là hai biểu thức ngoặc đúng có bậc là ~k_A, k_B~ thì ~AB~ cũng là một biểu thức ngoặc đúng có bậc bằng ~max(k_A, k_B)~.

Ví dụ "()[()]" là một biểu thức ngoặc đúng có bậc bằng ~2~.

Với hai số ~n~, ~k~ người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài đúng bằng ~n~ và có bậc không quá ~k~. Sắp xếp các biểu thức ngoặc này theo thứ tự từ điển, chú ý: '(' ~<~ ')' ~<~ '[' ~<~ ']' ~<~ '{' ~<~ '}'.

Yêu cầu: Cho ~n~, ~k~ và ~S~ là một biểu thức ngoặc đúng độ dài ~n~ và có bậc không quá ~k~, hãy tìm thứ tự của ~S~.

Input

• Dòng đầu chứa hai số nguyên ~n~, ~k~.
• Dòng thứ hai chứa xâu ~S~.

Output

• Một dòng duy nhất chứa một số nguyên là thứ tự của biểu thức ngoặc đúng ~S~.

Giới hạn

• Trong ~10\%~ test đầu tiên: ~n~, ~k \le 10~.
• Trong ~20\%~ test tiếp theo: ~n \le 20~, ~k \le 5~.
• Trong ~30\%~ test tiếp theo: ~n \le 100~, ~k \le 5~.

• Trong ~40\%~ test còn lại: ~n~, ~k \le 100~.

• ~n~ chẵn

• ~2 \times k \le n~

Sample Input

6 2
(()){}

Sample Output

4

Note

1. "(()())"
2. "(())()"
3. "(())[]"
4. "(()){}"