Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
- скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» — неправильные.
Вам даны две строки \(s\) и \(a\), длина строки \(s\) равна \(n\), длина строки \(a\) равна \(n - 3\). Строка \(s\) — скобочная последовательность (т. е. каждый элемент этой строки — либо символ открывающей скобки, либо символ закрывающей скобки). Строка \(a\) — бинарная (т. е. каждый элемент этой строки — либо 1, либо 0).
Строка \(a\) вводит ограничения на строку \(s\): для каждого \(i\), такого, что символ \(a_i\) — это 1, строка \(s_i s_{i+1} s_{i+2} s_{i+3}\) должна быть правильной скобочной последовательностью. Символы строки \(a\), равные 0, не вводят никаких ограничений.
Изначально строка \(s\) может не удовлетворять этим ограничениям. Чтобы это исправить, можно проводить следующую операцию любое кол-во раз: заменить некоторый символ \(s\) скобкой другого типа (то есть можно менять открывающие скобки на закрывающие и наоборот).
Определите, можно ли поменять некоторые символы в \(s\) таким образом, что она будет удовлетворять всем ограничениям, и если это возможно, посчитайте минимальное кол-во символов, которые надо заменить.
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество символов, которое нужно поменять в \(s\), или \(-1\), если все ограничения выполнить невозможно.