Maximize Parentheses Efficiency Score

The initial bracket string s keeps its relative order. Each bracket in kit can be used at most once and inserted at any position, and the profit is the sum of the scores of the brackets used. The final string must be balanced, and a solution is guaranteed to exist; scores can be negative, and inserting nothing is allowed. Find the maximum profit.

输入格式

The first line contains s, the second line kit, and the third line the score of each character of kit. The original text had no numeric bounds; this site uses 1≤length of both strings≤100000, −10^9≤score≤10^9, and balancing is guaranteed to be possible.

输出格式

Output a single integer, the answer.

样例 1

输入：

)((
)(()))
3 4 2 -4 -1 -3

输出：

6

样例 2

输入：

)
(
-7

输出：

-7

样例 3

输入：

()
()
5 -2

输出：

3

样例说明

The answers are 6, −7 and 3. A negative-score bracket must still be used if it is required to fix the original string; in the third example an extra pair can be inserted to gain 3.