Перед вами еще одна задача на правильные скобочные последовательности.
Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.
Вам задан шаблон скобочной последовательности, в котором присутствуют символы «(», «)» и «?». Вам надо заменить каждый символ «?» на скобку таким образом, чтобы получилась правильная скобочная последовательность.
Для каждого символа «?» в шаблоне известна стоимость замены его на «(» и «)». Ваша задача из всех возможных вариантов выбрать самый дешевый вариант.
Выходные данные
В первую строку выведите стоимость искомой последовательности. Во вторую выведите искомую последовательность.
Если решения не существует, выведите -1. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
(??)
1 2
2 8
|
4
()()
|