公平坚果与矩形

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定 $n$ 个矩形。第 $i$ 个矩形的四个顶点为 $(0,0),(x_i,0),(x_i,y_i),(0,y_i)$，并有代价 $a_i$。

你可以选择任意若干矩形，收益等于所选矩形的并集面积减去其代价之和。求最大可能收益。

保证不存在一个给定矩形包含另一个给定矩形。

输入格式

第一行包含整数 $n$。接下来 $n$ 行，每行包含 $x_i,y_i,a_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

数据范围

• $1\le n\le10^6$；
• $1\le x_i,y_i\le10^9$；
• $0\le a_i\le x_i y_i$；
• 不存在一个给定矩形包含另一个给定矩形。

本题采用独立测试点计分。