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。