問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

• 空文字列
• ある正しい括弧列 $A$ が存在して、(, $A$, ) をこの順に連結した文字列
• ある空でない正しい括弧列 $A$, $B$ が存在して、 $A$, $B$ をこの順に連結した文字列

空の文字列 $S$ があります。はじめ、あなたのスコアは $0$ であり、今から以下の操作を合計 $2N$ 回行います。

• $i$ 回目の操作では以下のどちらか一方を選択する。ここで $C_i$ は (または)である。
• $S$ の先頭に文字 $C_i$ を加え、スコアに $L_i$ を加算する。
• $S$ の末尾に文字 $C_i$ を加え、スコアに $R_i$ を加算する。

$2N$ 回の操作後の文字列 $S$ が正しい括弧列となるように操作を行うとき、最終的なスコアの最大値を求めてください。

この問題の制約下で $2N$ 回の操作後の文字列 $S$ が正しい括弧列となるような操作手順が存在することが示せます。

入力

$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$ は整数である。
• $1 \le N \le 10^5$
• $1 \le L_i,R_i \le 10^9$
• $C_i$ は(または)である。
• $C_1,C_2,\dots,C_{2N}$ の中に、(と)がそれぞれ $N$ 回ずつ出現する。

出力

スコアの最大値を出力してください。 最後に改行してください。

サンプル

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