Một dãy ngoặc đúng được định nghĩa như sau:

• Dãy rỗng là dãy ngoặc đúng

• Nếu ~A~ là dãy ngoặc đúng, thì ~(A)~ cũng là dãy ngoặc đúng

• Nếu ~A~ và B là dãy ngoặc đúng, thì ~AB~ là dãy ngoặc đúng.

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

Cho xâu ~S~ gồm các ký tự ~(~, ~)~ và ~?~. Với dấu ~?~ thứ ~i~, bạn được phép thay nó bằng dấu ~(~ hoặc ~)~,với chi phí lần lượt là ~Ai~, ~Bi~. Tìm cách thay các dấu ~?~ bằng ~(~ hoặc ~)~, với chi phí nhỏ nhất, sao cho xâu ~S~ trở thành dãy ngoặc đúng.

Input

Dòng đầu chứa xâu ~S~, độ dài không quá ~10^5~. Giả sử ~K~ là số dấu ~?~ trong xâu ~S~. ~K~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên dương ~Ai~, ~Bi~. ~(0 \le Ai, Bi \le 1000)~.

Output

Nếu không tìm được đáp án nào thỏa mãn, in ra -1, ngược lại, in ra một số nguyên duy nhất là kết quả của bài toán.

Sample Input

??
2 4
4 2

Sample Output

4