Скобочная последовательность — это строка, содержащая только символы «(» и «)». Правильная скобочная последовательность (или, коротко говоря, ПСП) — это скобочная последовательность, которая может быть преобразована в правильное арифметическое выражение путем вставки символов «1» и «+» между исходными символами последовательности. Например:
Вам задана строка \(s\), которая является ПСП. К этой строке можно применить любое количество операций. Каждая операция может иметь один из следующих типов:
Операция \(2\) может быть применена не более \(k\) раз. Посчитайте максимальное количество операций, которые можно применить, пока \(s\) не станет пустой.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^5\)) — количество наборов входных данных.
Каждый набор описывается двумя строками. Первая строка содержит два целых числа \(n\) и \(k\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le k \le n\); \(n\) четно) — длина \(s\) и максимальное количество операций типа \(2\), которые можно применить.
Вторая строка содержит \(s\) состоящую из \(n\) символов «(» и «)». Эта строка является ПСП.
Сумма \(n\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — максимальное количество операций, которые можно применить.
3 12 2 (()())((())) 6 3 ()()() 8 1 (((())))
4 3 2
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач