A string consisting only of parentheses ‘(’ and ‘)’ is called balanced if it satisfies one of the following conditions.
It is an empty string.
It is a concatenation of two non-empty balanced strings.
It is a concatenation of ‘(’, , and ‘)’, for some balanced string .
You are given characters of parentheses and integers . Then, you have to choose zero or more integers so that they satisfy the following conditions.
.
The concatenation of is a balanced string.
Note that the above conditions are always satisfied if you choose zero integers.
Your task is to maximize .
输入格式
The input consists of a single test case of the following format.
The first line consists of an integer (). The second line consists of characters , each of which is either ‘(‘ or ‘)’. The third line consists of integers ().
输出格式
Output in a line the maximum possible value of by choosing zero or more integers .
