Перед вами еще одна задача на правильные скобочные последовательности.
Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.
Вам задан шаблон скобочной последовательности, в котором присутствуют символы «(», «)» и «?». Вам надо заменить каждый символ «?» на скобку таким образом, чтобы получилась правильная скобочная последовательность.
Для каждого символа «?» в шаблоне известна стоимость замены его на «(» и «)». Ваша задача из всех возможных вариантов выбрать самый дешевый вариант.
В первой строке входного файла записан непустой шаблон четной длины, состоящий из символов «(», «)» и «?». Его длина не превосходит 5·104. Далее содержится m строк, где m — количество символов «?» в шаблоне. Каждая строка состоит из двух целых чисел ai и bi (1 leai, bi ≤ 106), где ai стоимость замены i-го символа «?» на открывающуюся скобку, а bi — на закрывающуюся.
В первую строку выведите стоимость искомой последовательности. Во вторую выведите искомую последовательность.
Если решения не существует, выведите -1. Если решений несколько, выведите любое.
(??)
1 2
2 8
4
()()
| Codeforces Beta Round 3 |
|---|
| Закончено |
