公平坚果堆积在平面世界中。他必须解决这个任务才能出去。
给定 $$$n$$$ 个矩形,其顶点位于 $$$(0, 0)$$$、$$$(x_i, 0)$$$、$$$(x_i, y_i)$$$、$$$(0, y_i)$$$。对于每个矩形,您还会获得一个数字 $$$a_i$$$。选择其中的并集面积减去所选的$$$a_i$$$之和最大的部分。
保证没有嵌套矩形。
Nut不知道如何找到答案,所以他请求你的帮助。
输入
第一行包含一个整数 $$$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$$$)。
保证没有嵌套矩形。
输出
在一行中打印问题的答案 - 您可以实现的最大值。
示例
输入 #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
注意
在第一个示例中,可以通过选择第一个和第二个矩形来获得正确答案。
在第二个示例中,也可以通过选择第一个和第二个矩形来获得正确答案。