Một dãy ngoăc đơn được gọi là dãy ngoặc đúng nếu ta thêm dấu + và số 1 vào nó thì ta được một biểu thức toán học đúng.

Ví dụ: "(())()", "()" là các dãy ngoặc đúng , còn ")(", "(()" and "(()))(" không phải là dãy ngoặc đúng.

Yêu cầu:

• Cho một chuỗi \(S\) chỉ gồm các kí tự ?, ) và (. Hãy thay tất cả các dấu ? có trong \(S\) bằng các kí tự ( hoặc ) với chi phí cho trước, sao cho \(S\) là một dãy ngoặc đúng và chi phí thay thế là nhỏ nhất.

Input

• Dòng thứ nhất chứa xâu \(S\) có độ dài không quá \(5.10^4\)

• \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(a_i,b_i(1\le a_i,b_i\le 10^6)\) - Trong đó: \(m\) là số lượng dấu ? có trong xâu \(S\), \(a_i\) là chi phí thay thế dấu ? thứ \(i\) bởi dấu ( còn \(b_i\) là chi phí thay thế dấu ? thứ \(i\) bởi )

Output

• Dòng thứ nhất chứa chi phí tối thiểu cần dùng

• Dòng thứ hai, in ra dãy ngoặc đúng tương ứng với chi phí trên.

Chú ý: Nếu có nhiều đáp án thoả mãn yêu cầu bài toán, in ra bất kì, ngược lại nếu không có cách thay thế nào thoả mãn, in ra -1

Example

((??()))??
1 2
2 3
3 4
4 1

8
(()(()))()