这是一个规则的字符括号序列。一个括号序列是规则的，那么在序列里面插入‘+’ 和 ‘1’ 会得到一个正确的数学表达式。

合法：(())()， ()，(()(()))

不合法：)(，(()，(()))(

给你一个字符序列，里面包含‘（’，‘）’ 和‘？’

我们需要替换所有的‘？’，替换为“（” 和 ‘）’，在所有可能中找到花费最小的。

输入数据：

首先是一个字符串。

然后是m行，每行两个数字ai, 和 bi。

分别代表将第i个问号换为'(' 和‘）’ 的花费。

如果不能得到匹配的串则输出 -1.

==================================================================================================================================================================================

题目解析：

我们遍历串，把所有‘？’变为‘）’, 我们使用一个计数器 cnt, 遇到‘（’ 就 +1， 遇到‘）’ 就 -1.

当我们的cnt为 负数的时候，说明我们必须把前面的一个‘）’变为‘（’才行，这个时候我们需要一个优先队列来存储最优值。其余的自己想想应该就明白了。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

#include <queue>

using namespace std;

typedef __int64 LL;

const LL INF = 1e9+;

const LL MOD = 1e9+;

const LL maxn = ;

char str[maxn];

LL n;

struct node

{

    int a, b, c;

    int Index;

    bool friend operator < (node B,node A)

    {

        return A.c < B.c;

    }

} P[maxn];

LL solve()

{

    LL k = , ans = , cnt = ;

    priority_queue<node> Q;

    node Pn;

    for(int i=; str[i]; i++)

    {

        if(str[i] == '?')

        {

            Q.push(P[k]);

            ans += P[k].b;

            str[i] = ')';

            k ++;

            cnt --;

        }

        else if(str[i] == '(')

            cnt ++;

        else

            cnt --;

        if(cnt < )

        {

            while(Q.size() && cnt < )

            {

                Pn =  Q.top();

                Q.pop();

                cnt += ;

                ans = ans - Pn.b + Pn.a;

                str[Pn.Index] = '(';

            }

        }

        if(cnt < )

            return -;

    }

    if(cnt > )

        return -;

    return ans;

}

int main()

{

    scanf("%s", str);

    for(int i=; str[i]; i++)

    {

        if(str[i] == '?')

        {

            scanf("%d %d", &P[n].a, &P[n].b);

            P[n].c = P[n].a - P[n].b;

            P[n ++].Index = i;

        }

    }

    LL ans = solve();

    printf("%I64d\n", ans);

    if(ans != -)

        puts(str);

    return ;

}