D. 滑雪

山上一共有$n$个缆车站点，每个站点有一个整数$a_i$，表示第$i$个站点的风景愉悦度。

为了不走回头路，游客A只坐向下的缆车，而且路线要呈Z型，这样可以看到更多的风景，并且更快到达山底，游客A可以从山顶步行到任意一个缆车站点开始坐车，并且可以在任一缆车站点停下来开始走路到山底。

对于这些站点的位置，我们可以把山看作平面$y-z=0$，$y$越大，站点越高，满足条件的缆车路线就是相邻的缆车站点满足$y_{i-1}>y_i, x_{i-1}\neq x_i$,相邻的三个站点满足：$(x_{i-2}-x_{i-1})(x_{i-1}-x_i)<0$。

你可以帮助游客A快速算出，游客A可得到的风景愉悦度之和的最大值吗？

输入文件中的第一行为一个正整数$n$。

接下来的$n$行，每行有三个整数$x_i$，$y_i$，$a_i$，分别表示$(x_I,y_i)$处有一个风景愉悦度为$a_i$的缆车站点。

输出文件中仅一行为一个整数，表示游客A可得到的风景愉悦度之和的最大值。

输入样例

4
6 4 8
1 3 -1
2 2 -2
4 1 4

输出样例

12

对于所有的测试数据： $n\leq 50000$ 且 $-100000\leq x,y\leq 100000,-1000\leq a\leq1000$，且$y_i=y_j$当且仅当$i=j$。