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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class C4C3 {
	private StringTokenizer st;
	private BufferedReader bf;
	private int n;
	private String s;
	private List<Node> tbl; 
	private long rcost;
	private String rs;
	private PriorityQueue<Node> q;
	
	private static class Node implements Comparable<Node> {
		int scost;
		int ccost;
		int index;
		int delta;
		boolean dirty;
		
		public Node() {}
		public Node(int a, int b, int c) {
			scost = a;
			ccost = b;
			index = c;
			delta = a - b;
			dirty = false;
		}
		
		public int compareTo(Node that) {
			return this.delta - that.delta;
		}
	}
	
	public C4C3() {
		tbl = new ArrayList<Node>();
		q = new PriorityQueue<Node>();
//		readData();
		
		try {
			bf = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(bf.readLine());

			s = next();
			n = s.length();

			long cost = 0;
			//head and tail
//			if (s.charAt(0) == '?') {
//				s = s.replaceFirst("\\?", "(");
//				cost += tbl.get(0).scost;
//			}
//			if (s.charAt(n-1) == '?') {
//				char[] ac = s.toCharArray();
//				ac[n-1] = ')';
//				s = new String(ac);
//				cost += tbl.get(tbl.size()-1).ccost;
//			}
//			
//			if (isValidBracket(s)) {
//				rcost = cost;
//				rs = s;
//				System.out.println(cost);
//				System.out.println(s);
//				return;
//			}
			
			
			char[] ca = s.toCharArray();
			long delta = 0;
	        for (int i = 0; i < n; i++)
	        {
	            if ( ca[i] == '(' ) delta++;
	            if ( ca[i] == ')' ) delta--;
	            if ( ca[i] == '?' )
	            {
            		int scost = nextInt();
            		int ccost = nextInt();
            		if (i == 0) {
            			ca[i] = '(';
            			cost += scost;
            			delta++;
            		} else {
	            		ca[i] = ')';
	//	            		int scost = nextInt();
	//	            		int ccost = nextInt();
	            		cost += ccost;
	            		delta--;
	            		q.add(new Node(scost, ccost, i));
            		}
	            }
	            if ( delta < 0 )
	            {
	                if ( q.size() == 0 )
	                {
	    	        	rcost = -1;
	    	        	System.out.println(-1);
	                }
	                ca[q.peek().index] = '(';
	                cost += q.peek().delta;
	                q.poll();
	                delta += 2;
	            }
	        }
	        if (delta != 0) {
	        	rcost = -1;
	        	System.out.println(-1);
	        }
	        else
	        {
	        	rcost = cost;
	        	rs = new String(ca);
	        	System.out.println(cost);
	        	System.out.println(new String(ca));
	        }
			
		} catch (Exception e) {
			e.printStackTrace();
		}

		//		simulate(cost);	
	}
	
	private void simulate(int cost) {
		int tmpcost = cost;
		char[] ca = s.toCharArray();
		//temporary set ')'
		for (int i = 0; i < tbl.size(); i++) {
			int ind = tbl.get(i).index;
			if (ind == 0 || ind == (n -1))
				continue;
			
			ca[ind] = ')';
			tmpcost += tbl.get(i).ccost;				
		}
		
		//table sort by cost delta
		Collections.sort(tbl);
		
		//check string
		int delta = 0;
		int sindex = 0;
		int eindex = 0;
		for (int j = 0; j < n; j++) {
			eindex = j;
			switch (ca[j]) {
			case '(':
				delta++;
				break;
			case ')':
				delta--;
				break;
			}
			if (delta < 0) {
				for (int i = 0; i < tbl.size(); i++) {
					int ind = tbl.get(i).index;
					if (ind == 0 || ind == (n -1))
						continue;
					
					//current check range
					if (!(ind >= sindex && ind <= eindex))
						continue;

					if (tbl.get(i).dirty)
						continue;
						
					ca[ind] = '(';
					tmpcost += tbl.get(i).delta; //tbl.get(i).ccost - (tbl.get(i).scosttbl.get(i).ccost)
					tbl.get(i).dirty = true;
					delta++;
					delta++;
					break;
				}
			}
		}
		
		String tmp = new String(ca);
		if (isValidBracket(tmp)) {
			rcost = tmpcost;
			rs = tmp;
			System.out.println(tmpcost);
			System.out.println(tmp);
			return;
		} else {
			rcost = -1;
			System.out.println(-1);
		}
	}
	
	public String results() {
		return rs;
	}
	public long resultc() {
		return rcost;
	}
	
	private boolean isMinus(char[] ca, int i) {
		int delta=0;
		for (int j = 0; j < s.length(); j++) {
			switch (ca[j]) {
			case '(':
				delta++;
				break;
			case ')':
				delta--;
				break;
			}
			if (delta < 0)
				return true;
		}
		if (delta < 0)
			return true;
		else
			return false;
	}
	
	
	private void readData() {
		try {
			bf = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(bf.readLine());

			s = next();
			n = s.length();
//			for (int i = 0; i < n; i++) {
//				if (s.charAt(i) == '?') {
//					int sc = nextInt();
//					int cc = nextInt();
//					tbl.add(new Node(sc, cc, i));
//				}
//			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private boolean isValidBracket(String s) {
		int delta = 0;
		for (int i = 0; i < s.length(); i++) {
			switch (s.charAt(i)) {
			case '(':
				delta++;
				break;
			case ')':
				delta--;
				break;
			case '?':
				return false;
			}
			if (delta < 0)
				return false;
		}
		if (delta == 0)
			return true;
		else
			return false;
	}
	
	private int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	private String next() throws IOException {
		if (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(bf.readLine());
		return st.nextToken();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		C4C3 c = new C4C3();
	}

}
