D. Скобочная последовательность
ограничение по времени на тест
1 second
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Перед вами еще одна задача на правильные скобочные последовательности.

Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.

Вам задан шаблон скобочной последовательности, в котором присутствуют символы «(», «)» и «?». Вам надо заменить каждый символ «?» на скобку таким образом, чтобы получилась правильная скобочная последовательность.

Для каждого символа «?» в шаблоне известна стоимость замены его на «(» и «)». Ваша задача из всех возможных вариантов выбрать самый дешевый вариант.

Входные данные

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

Выходные данные

В первую строку выведите стоимость искомой последовательности. Во вторую выведите искомую последовательность.

Если решения не существует, выведите -1. Если решений несколько, выведите любое.

Примеры
Входные данные
(??)
1 2
2 8
Выходные данные
4
()()