Скобочная последовательность — это строка, содержащая только символы «(» и «)». Правильная скобочная последовательность (или, коротко говоря, ПСП) — это скобочная последовательность, которая может быть преобразована в правильное арифметическое выражение путем вставки символов «1» и «+» между исходными символами последовательности. Например:
- скобочные последовательности «()()» и «(())» являются правильными (возможные выражения: «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» не являются правильными.
Вам задана строка \(s\), которая является ПСП. К этой строке можно применить любое количество операций. Каждая операция может иметь один из следующих типов:
- выбрать некоторый непустой префикс \(s\) и удалить его из \(s\), так что \(s\) все еще остается ПСП. Например, можно применить эту операцию следующим образом: «(())()(())()()» \(\to\) «()()» (первые \(10\) символов были удалены);
- выбрать некоторую непрерывную непустую подстроку \(s\) и удалить ее из \(s\), так что \(s\) все еще остается ПСП. Например, можно применить эту операцию следующим образом: «(())()(())()()» \(\to\) «(())()()()» (символы с \(7\)-го по \(10\)-й были удалены).
Операция \(2\) может быть применена не более \(k\) раз. Посчитайте максимальное количество операций, которые можно применить, пока \(s\) не станет пустой.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество операций, которые можно применить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
12 2
(()())((()))
6 3
()()()
8 1
(((())))
|
4
3
2
|