Problem Statement

A string satisfying any of the following conditions is defined as a correct bracket sequence.

• The empty string
• The string obtained by concatenating (, $A$, ) in this order, for some correct bracket sequence $A$
• The string obtained by concatenating $A$, $B$ in this order, for some non-empty correct bracket sequences $A$, $B$

There is an empty string $S$. Initially, your score is $0$, and you will now perform the following operation a total of $2N$ times.

• In the $i$-th operation, choose one of the following. Here, $C_i$ is ( or ).
• Add the character $C_i$ to the beginning of $S$, and add $L_i$ to the score.
• Add the character $C_i$ to the end of $S$, and add $R_i$ to the score.

When performing the operations so that the string $S$ after the $2N$ operations is a correct bracket sequence, find the maximum possible final score.

It can be shown that, under the constraints of this problem, there exists a sequence of operations such that the string $S$ after the $2N$ operations is a correct bracket sequence.

Input

$N$
$C_1\ L_1\ R_1$
$C_2\ L_2\ R_2$
$\vdots$
$C_{2N}\ L_{2N}\ R_{2N}$

• $N, L_i, R_i$ are integers.
• $1 \le N \le 10^5$
• $1 \le L_i,R_i \le 10^9$
• $C_i$ is ( or ).
• Among $C_1,C_2,\dots,C_{2N}$, each of ( and ) appears exactly $N$ times.

Output

Output the maximum score. Print a newline at the end.

Sample

2
( 5 1
) 10 1
( 1 7
) 100 100

116

7
) 5 83
( 39 31
) 96 66
) 53 55
( 22 42
) 82 72
) 89 71
( 98 47
( 8 32
( 19 75
) 69 63
( 29 78
( 26 37
) 48 66

890