← 返回题目列表

Codeforces · 1083/E

E. 公平坚果和矩形

中文机器翻译题面 查看原题

公平坚果堆积在平面世界中。他必须解决这个任务才能出去。

给定 $$$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

注意

在第一个示例中,可以通过选择第一个和第二个矩形来获得正确答案。

在第二个示例中,也可以通过选择第一个和第二个矩形来获得正确答案。