题号：NC52866
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld
题目描述
Bobo has a very long sequence divided into n consecutive groups.
The i-th group consists of
copies of character 
where is either "`(`" or "`)`".
As the sequence may not be valid parentheses sequence, Bobo can change a character in the i-th group from "`(`" to "`)`" (and vice versa) with cost
.
He would like to know the minimum cost to transform the sequence into a valid one.
Note:
- An empty string is valid.
- If S is valid, (S) is valid.
- If U, V are valid, UV is valid.
The i-th group consists of
As the sequence may not be valid parentheses sequence, Bobo can change a character in the i-th group from "`(`" to "`)`" (and vice versa) with cost
He would like to know the minimum cost to transform the sequence into a valid one.
Note:
- An empty string is valid.
- If S is valid, (S) is valid.
- If U, V are valid, UV is valid.
输入描述:
The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains an integer n.
The i-th of the following n lines contains.
*
*
*is even.
*
* The sum of n does not exceed.
输出描述:
For each case, output an integer which denotes the result.
示例1
备注:
For the first sample, Bobo should change only the character in the second group.
For the second sample, Bobo should change half of characters in both groups.