Time Limit: 1000 mSec Memory Limit : 32768 KB

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?

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.

For each case,

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

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

-1
73