Problem1452--括号匹配Ⅱ

1452: 括号匹配Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 130  Solved: 33
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI最近学会了括号匹配,而POPO为了验明他的学习成果,决定给他来一道括号匹配plus版。
已知POPO会给出只包含'('、')'、'?’三种字符的字符串,对于每个'?’字符,POPO会给出把其变成'('字符与')'字符的代价。
请问PIPI将所有的'?’字符替换后,使得最终括号序列合法的最小代价是多少。 

Input

第一行一个字符串,1<=字符串长度<=10^5。
接下来m行,每行两个正整数ai和bi。m表示字符串中'?'字符的数量,ai表示把从左到右第i个'?'字符变成'('字符的代价,bi表示把从左到右第i个'?'字符变成')'字符的代价。其中0<=m<=字符串长度,ai<=10^9,bi<=10^9。

Output

输出使得最终括号序列合法的最小代价。若PIPI无法使得最终括号序列合法,输出-1。

Sample Input

(??)
1 2
2 8

Sample Output

4

Source/Category