题目描述

JP 不好好训练，又喜欢上了另一个游戏——寻宝。

游戏里有 $n$ 处宝藏，它们被埋在一个无限大的二维网格中。每个宝藏都有价值 $P_i$，位置是 $(x_i,y_i)$。

如果网格 $(x,y)$ 满足下面两个条件之一，则它是可挖掘的：

• $y=-1$。

• $(x-1,y+1),(x,y+1),(x+1,y+1)$ 这三个方格都已经被挖掘了。

挖掘一个方格的代价为 $1$。当一个宝藏被挖掘出来时，就认为已经获得了它的价值。请你帮 JP 求出所能得到的最大利润，也即价值减代价。（可能一个宝藏也不挖，利润为 $0$）

输入格式

第一行为 $n$，表示宝藏数量。

接下来 $n$ 行，每行三个整数 $x_i,y_i,P_i$ 表示宝藏的位置和价值。

输出格式

一行一个整数，表示最大利润。

5
1 -1 2
0 -1 2
4 -1 1
3 -1 2
2 -1 2

4

提示

样例解释 1

挖 $1,2,4,5$ 号宝藏，价值为 $8$，花费代价为 $4$，所以利润为 $4$。可以证明没有更优的方案。

数据范围

对于 $30\%$ 的数据，$n\leq 15$。

对于 $50\%$ 的数据，$-10^3\leq y_i\leq 0$。

对于 $100\%$ 的数据，$n\leq 10^3,-10^4\leq x_i\leq 10^4,-10^4\leq y_i<0,1\leq P_i\leq 10^6$。