Treasure Hunters#5529
After extensive searching, the treasure hunters have discovered a vast field containing points, each with golden treasures. The leader possesses a map that shows the coordinates and the amount of gold at each treasure location. The field is represented as a set of points on a rectangular coordinate plane, where all ordinates are positive integers. The treasure hunters' camp is located along the -axis. The coordinates of the treasure points are integers.
The leader has devised a secret plan: he will start at any point in the field with integer coordinates and make his way to the camp. To avoid drawing attention from other treasure hunters, he will move from each point only to one of the following: (x-1, y-1), (x, y-1), or (x+1, y-1). As he passes a point with a treasure, he will quietly collect all the gold there. The leader will stop once he reaches the -axis. Determine the maximum amount of gold the leader can gather by following this plan.
The first line contains an integer (3 \leq N \leq 50000). Each of the following lines contains three integers x_i, y_i, c_i — the coordinates of the -th treasure and the amount of gold it contains, respectively. The coordinate of each treasure satisfies -1000000000 \leq x \leq 1000000000. The coordinate of each treasure satisfies 1 \leq y \leq 1000000000. The amount of gold in each treasure is an integer in the range [1, 10^9].
Output a single integer — the maximum amount of gold the leader can collect.
Example 1