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
Bình luận