CF1083E The Fair Nut and Rectangles

Fair Nut 被困在了平面世界。他需要解决这个任务才能脱困。 给定 $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$）。 保证不存在嵌套的矩形。

输出一行，表示你能获得的最大值。

在第一个样例中，选择第一个和第二个矩形可以得到最优答案。 在第二个样例中，选择第一个和第二个矩形也可以得到最优答案。 由 ChatGPT 4.1 翻译