Least Cost Bracket Sequence CodeForces - 3D

题目描述

This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

Input

The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. Then there follow m lines, where m is the number of characters "?" in the pattern. Each line contains two integer numbers a i and b i (1 ≤ a i,  b i ≤ 106), where a i is the cost of replacing the i-th character "?" with an opening bracket, and b i — with a closing one.

Output

Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print -1, if there is no answer. If the answer is not unique, print any of them.

Examples

Input

(??)
1 2
2 8

Output

4
()()

分析

一句话题意：:给一个序列，序列里面会有左括号、问号、右括号。对于一个?而言，可以将其替换为一个(，也可以替换成一个)，但是都有相应的代价。问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。

这道题要用到贪心的思想，我们可以先遍历一遍，把所有的问号都改成右括号

然后我们再从左到右进行匹配，同时记录一下左括号的个数\(cnt\)，如果当前遍历到了一个右括号，那么\(cnt\)-- 代表有一对括号匹配成功

如果\(cnt<0\)那么我们就从之前由问号变成的右括号中找一个，把它变成左括号，同时把\(cnt+2\)

那么我们找哪一个呢？肯定是找变成左括号的价值减去变成右括号的价值最小的那一个，我们可以用一个优先队列维护

要是找不到就说明匹配失败，直接输出\(-1\)

最后循环结束的时候如果左括号的个数不为0，也要输出\(-1\)

否则就输出你记录的字符串

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
char s[maxn],s2[maxn];
struct asd{
    int lef,rig,num;
    asd(int aa=0,int bb=0,int cc=0){
        lef=aa,rig=bb,num=cc;
    }
    bool operator < (const asd& A) const {
        return (lef-rig)>(A.lef-A.rig);
    }
};
priority_queue<asd> q;
int main(){
    scanf("%s",s);
    int n=strlen(s);
    int cnt=0;
    long long ans=0;
    for(int i=0;i<n;i++){
        if(s[i]=='('){
            cnt++;
            s2[i]='(';
        }
        else{
            cnt--;
            s2[i]=')';
            if(s[i]=='?'){
                int aa,bb;
                scanf("%d%d",&aa,&bb);
                ans+=(long long)bb;
                q.push(asd(aa,bb,i));
            }
            if(cnt<0){
                if(q.empty()){
                    printf("-1\n");
                    return 0;
                }
                cnt+=2;
                int ll=q.top().lef,rr=q.top().rig,id=q.top().num;
                s2[id]='(';
                q.pop();
                ans+=(long long)(ll-rr);
            }
        } 
    }
    if(cnt!=0) printf("-1\n");
    else printf("%lld\n%s\n",ans,s2);
    return 0;
}