This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

Input

The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. Then there follow m lines, where m is the number of characters "?" in the pattern. Each line contains two integer numbers ai and bi (1 ≤ ai, bi ≤ 106), where ai is the cost of replacing the i-th character "?" with an opening bracket, and bi — with a closing one.

Output

Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print -1, if there is no answer. If the answer is not unique, print any of them. 

Examples

Input

(??)
1 2
2 8


Output

4
()()
# coding: utf-8

"""
题解
判断一个括号序列是否合法常见的有两种方式，栈和前缀和。
使用前缀和时，初始化一个计数器为0，从左向右扫描序列，遇到左括号时计数器加一，右括号计数器减一。扫描过程中，计数器的值不能出现负数；扫描完成后，计数器的和为0，此时这个序列满足括号匹配规则。
这道题使用这种思路来做，就是一个贪心问题。
我们先将所有 ? 都当做右括号来处理。从左向右扫描序列，当计数器变为负数时，将左边的一个 ? 变为左括号，计数器加2 ，扫描完成后检查计数器是否为0。
考虑到这道题还要求替换成本最小，因此选择 ? 变为左括号时，要选择变完之后成本最小的那个。这里可以使用一个优先队列来存储 ? 替换为左右括号的成本，减少插入和获取的时间。
"""

from heapq import heappush, heappop

def solution():
    line = raw_input() # 输入的原始序列
    result = []  # 替换后的结果
    cost = 0 # 替换后的总成本
    priority_queue = [] # 优先队列
    cnt = 0 # 计数器
    for index, char in enumerate(line):
        if char == '(':
            result.append(char)
            cnt += 1
        else:
            result.append(')')
            cnt -= 1
            # 读到问号，从标准输入获取替换成本，放入优先队列
            if char == '?':
                left_cost, right_cost = map(int, raw_input().split())
                heappush(priority_queue, (left_cost - right_cost, index))
                cost += right_cost  # 问号默认先按右括号处理

            if cnt < 0:
                if not priority_queue:  # 计数器出现负数，又没有 ? 可以替换为左括号
                    break

                # 挑选从右括号变为左括号后，成本减小最大的那个问号，贪心
                tmp_cost, tmp_index = heappop(priority_queue)
                cost += tmp_cost
                result[tmp_index] = '('
                cnt += 2

    if cnt != 0:
        print -1
    else:
        print cost
        print ''.join(result)


if __name__ == '__main__':
    solution()