Find Max To Balance

The original bracket string scores 0. Each bracket in kit has its own rating and can be used at most once, and you may choose none; insert the chosen brackets anywhere in the original string, keeping the original order, to get a balanced bracket string, and maximize the total rating of the chosen brackets. Completion is guaranteed to be possible.

输入格式

The first line contains the original string s, the second line contains kit, and the third line contains the rating of each character of kit. This site sets 1≤|s|,|kit|≤100000 and ratings in −10^9..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

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

输出：

1

样例 2

输入：

)
(
-5

输出：

-5

样例 3

输入：

()
()
-1 -2

输出：

0

样例说明

Example 1: choose the left bracket rated 4 and the right bracket rated −3 for a gain of 1; choosing one more pair would lower the total. Example 2: the only left bracket must be added, so the answer is −5. Example 3: the original string is already balanced, so choosing no brackets gives 0.