CF1083E.The Fair Nut and Rectangles

The Fair Nut got stacked in planar world. He should solve this task to get out.

You are given $n$ rectangles with vertexes in $(0, 0)$, $(x_i, 0)$, $(x_i, y_i)$, $(0, y_i)$. For each rectangle, you are also given a number $a_i$. Choose some of them that the area of union minus sum of $a_i$ of the chosen ones is maximum.

It is guaranteed that there are no nested rectangles.

Nut has no idea how to find the answer, so he asked for your help.

公平的坚果被困在了一个平面世界中。他必须解决这个问题才能脱身。

给你 $n$ 个矩形，每个矩形的四个顶点分别为 $(0, 0)$、$(x_i, 0)$、$(x_i, y_i)$ 和 $(0, y_i)$。对每个矩形，你还给定一个数 $a_i$。你需要从中选出若干个矩形，使得这些矩形的并集面积减去所选矩形对应 $a_i$ 的总和达到最大值。

题目保证不存在互相嵌套的矩形（即任意两个矩形均不满足一个完全包含于另一个之内）。

坚果完全不知道如何求解，因此向你求助。

The first line contains one integer $n$ ($1 \leq n \leq 10^6$) — the number of rectangles.

Each of the next $n$ lines contains three integers $x_i$, $y_i$ and $a_i$ ($1 \leq x_i, y_i \leq 10^9$, $0 \leq a_i \leq x_i \cdot y_i$).

It is guaranteed that there are no nested rectangles.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 矩形的数量。

接下来的 $n$ 行中，每行包含三个整数 $x_i$、$y_i$ 和 $a_i$（$1 \leq x_i, y_i \leq 10^9$，$0 \leq a_i \leq x_i \cdot y_i$）。

保证不存在嵌套的矩形。

In a single line print the answer to the problem — the maximum value which you can achieve.

在一行中输出问题的答案——你能达到的最大值。

In the first example, the right answer can be achieved by choosing the first and the second rectangles.

In the second example, the right answer can also be achieved by choosing the first and the second rectangles.

在第一个例子中，通过选择第一个和第二个矩形可以得到正确答案。

在第二个例子中，通过选择第一个和第二个矩形也可以得到正确答案。