問題文

明日はクリスマスです。あなたは、クリスマスパーティのためのケーキを$N$個買いました。
$i$ 個目のケーキの形は、奥行きが $A_i$ cm, 幅が $B_i$ cm, 高さが $10$ cm の直方体であり、カロリーは $C_i$ kcal です。
あなたは持っているケーキを材料にして、できるだけ高いカロリーをもつ"再帰的ケーキ"を作ろうと考えました。

再帰的ケーキの再帰的定義は以下のとおりです。

• 1つのケーキからなるもの
• 再帰的ケーキの最上面に、「最上面の奥行き・幅より小さな奥行き・幅を持つケーキ」を回転させずに1つのせたもの
  (つまり、上部のケーキを $i$ 個目、下部のケーキを $j$ 個目とすると、$A_i < A_j$ かつ $B_i < B_j$ が成り立つようにケーキをのせていく)

再帰的ケーキのカロリーは、再帰的ケーキを構成するケーキのカロリーの合計になります。

作ることのできる再帰的ケーキのカロリーの最大[kcal]を求めてください。

入力

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
…
$A_N$ $B_N$ $C_N$

• $1\leq N\leq 200000$
• $1\leq A_i, B_i, C_i \leq 10^9$
• $N, A_i, B_i, C_i$ は整数

出力

作ることのできる再帰的ケーキのカロリーの最大[kcal]を1行目に出力してください。 最後に改行してください。

部分点

この問題には部分点は設定されていませんが、入力ケースは以下の区分に分かれています。

• $1\leq N\leq 16$ かつ $C_i = 1$
• $1\leq N\leq 16$
• $1\leq N\leq 2000$ かつ $C_i = 1$
• $1\leq N\leq 2000$
• $1\leq N\leq 200000$ かつ $C_i = 1$
• $1\leq N\leq 200000$ (満点)

サンプル

3
4 7 1
5 9 1
8 5 1

2

4
4 7 2
5 9 3
8 5 4
10 10 2

7

4
4 7 1
5 9 2
8 5 4
10 10 2

6

3
5 5 7
5 7 5
7 5 5

7