markdown

E. 公平坚果与矩形

每个测试点的时间限制：$2$ 秒
每个测试点的内存限制：$256$ MB
输入：标准输入
输出：标准输出

公平坚果被困在了平面世界中。他需要解决这个问题才能离开。

给定 $n$ 个矩形，每个矩形的顶点分别为 $(0,0)$、$(x_i,0)$、$(x_i,y_i)$、$(0,y_i)$。对于每个矩形，还给定了一个权值 $a_i$。你需要选择其中一些矩形，使得它们的并集面积减去所选矩形的权值之和的值最大。

保证输入的矩形之间不存在嵌套关系。

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

输入

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

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

保证输入的矩形之间不存在嵌套关系。

输出

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

样例

输入样例 1

3
4 4 8
1 5 0
5 2 10

输出样例 1

9

输入样例 2

4
6 2 4
1 6 2
2 4 3
5 3 8

输出样例 2

10

注释

在第一个样例中，选择第一个和第二个矩形可以得到最优解。
在第二个样例中，选择第一个和第二个矩形同样可以得到最优解。