提示: 欢迎访问OurACM平台。
Problem 1880 MiniCost

Accept: 194    Submit: 484
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A regular brackets sequence is defined in the following way:

1.Empty sequence is a regular sequence.

2.If S is a regular sequence, then (S) is also a regular sequence.

3.if a and b are regular brackets sequences, then ab is a regular brackets sequence.

4.no other sequence is a regular brackets sequence

Now you will be given a brackets sequence S consist of '(' and ')'. You are required to produce a regular sequence with it.

You can make some changes on the sequence. Each time you can choose a position x and switch the character S[x] to the opposite(ie,from '(' to ')' and vice versa) with a cost of C[x].

What's the minicost to obtain a regular sequence?

Input

There are multiple cases, for each case,

the first line is the sequence string S (1 <= SIZE(S) <= 1000)

Then following SIZE(S) integers (C[1],C[2],...,C[N]) 0 <= C[i] <= 1000.

There maybe one or more lines between each case.

Output

For each case,

if you can obtain a regular sequence,output the minicost,or output -1 instead.

Sample Input

()( 33 78 84 ())( 63 73 55 18

Sample Output

-1 73

Source

code6

Submit  Back  Status  Discuss