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
()()

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * CodeForces Round 3D. Least Cost Bracket Sequence
 * Created by Darren on 14-9-4.
 *
 * Tag: greedy
 */
public class Main {
    Reader in = new Reader(System.in);
    PrintWriter out = new PrintWriter(System.out, true);

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    char[] seq;
    int n;

    void run() throws IOException {
        seq = in.readLine().toCharArray();
        n = seq.length;

        if ((n&1) == 1) {   // Irregular bracket sequence
            out.println(-1);
            return;
        }

        // Cost changes by replacing closing brackets with opening ones
        PriorityQueue<Mark> maxHeap = new PriorityQueue<Mark>();

        int balance = 0;
        long cost = 0;
        for (int i = 0; i < n; i++) {
            if (seq[i] == '(') {
                balance++;
            } else if (seq[i] == ')') {
                balance--;
            } else {    // seq[i] = '?'
                seq[i] = ')';   // Assume putting closing bracket
                balance--;
                int costLeft = in.nextInt(), costRight = in.nextInt();
                cost += costRight;
                maxHeap.offer(new Mark(i, costLeft-costRight));
            }

            if (balance < 0) {      //
                if (maxHeap.size() == 0) {
                    out.println(-1);
                    return;
                }
                Mark mark = maxHeap.poll();
                seq[mark.position] = '(';
                cost += mark.diff;
                balance += 2;
            }
        }

        if (balance == 0) {
            out.println(cost);
            out.println(seq);
        } else {
            out.println(-1);
        }
    }

    class Mark implements Comparable<Mark>{
        int position;
        int diff;

        public Mark(int position, int diff) {
            this.position = position;
            this.diff = diff;
        }

        @Override
        public int compareTo(Mark o) {
            return this.diff - o.diff;
        }
    }

    static class Reader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public Reader(InputStream input) {
            reader = new BufferedReader(new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /** get next word */
        String nextToken() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer( reader.readLine() );
            }
            return tokenizer.nextToken();
        }

        String readLine() throws IOException {
            return reader.readLine();
        }

        char nextChar() throws IOException {
            return (char)reader.read();
        }

        int nextInt() throws IOException {
            return Integer.parseInt( nextToken() );
        }

        long nextLong() throws IOException {
            return Long.parseLong( nextToken() );
        }

        double nextDouble() throws IOException {
            return Double.parseDouble( nextToken() );
        }
    }
}
