P14068 [PO Final 2022] 搭塔 / Legobyggartävlingen

你和你的宿敌 Gohu 参加了一场乐高搭建比赛。你们沿着 $x$ 轴建造了许多高低不一、精致程度不同的塔，正等着评委到来。评分规则如下：如果你的某座塔的精致度为 $f$，高度为 $h$（以乐高块计），那么你将为这座塔得到 $f \cdot h$ 分。配图对应样例 2。 ::::align{center}  :::: 这场比赛举世闻名，因此有许多无人机来回飞行拍摄这些漂亮的塔。为了避免无人机与塔相撞（从而把与其相撞的那一块及其上方的所有乐高块都撞掉），摄制组沿着 $x$ 轴放置了许多高度各异的无线电桅杆。无人机每向前移动一格，可以向上或向下移动一格，并且总是尽量贴近地面飞行（以获得更好的画面），但绝不会低于任何桅杆的高度飞行。 突然，摄制组把目光移开了！你决定迅速移除一些桅杆，让无人机开始撞上这些塔。你应该移除哪些桅杆，才能使你的收益最大化（即你的得分减去 Gohu 的得分的差值最大）？ 当无人机撞上某座塔时，这座塔的精致度不会降低，只有高度会降低。保证初始放置的桅杆使得无人机不会与任何塔相撞。

第一行包含三个整数 $A, B, M$（$1 \le A, B, M \le 2000$）——你建造的塔的数量、Gohu 建造的塔的数量以及桅杆的数量。 接下来有 $A$ 行，每行包含整数 $x, f, h$（$1 \le x \le 10^6,\ 1 \le f \le 100,\ 1 \le h \le 10000$）——你的一座塔的 $x$ 位置、精致度和高度。 然后有 $B$ 行，每行包含整数 $x, f, h$（$1 \le x \le 10^6,\ 1 \le f \le 100,\ 1 \le h \le 10000$）——Gohu 的一座塔的 $x$ 位置、精致度和高度。 接着有 $M$ 行，每行包含整数 $x, h$（$1 \le x \le 10^6,\ 1 \le h \le 10000$）——一根桅杆的 $x$ 位置和高度。 任意两座塔不会有相同的 $x$ 值，任意两根桅杆也不会有相同的 $x$ 值；但桅杆可以与塔共享相同的 $x$ 位置。

输出一个整数：在最优选择要移除的桅杆后，你所能达到的最大值（你的得分）$-$（Gohu 的得分）。

### 样例解释 ::::align{center}  图 1：样例 1 :::: ::::align{center}  图 2：样例 2 :::: ::::align{center}  图 3：样例 3 :::: 在所有图片中，你的塔用蓝色表示，Gohu 的塔用红色表示。 在样例 1 中，最优做法是只移除第 1 根桅杆。此后你得到 $2$ 分，Gohu 得到 $0 + 1$ 分，差值为 $1$ 分。 在样例 2 中，最优做法是移除第 2、3 根桅杆。此后你得到 $500 + 30 + 120 = 650$ 分，Gohu 得到 $400 + 30 = 430$ 分，差值为 $220$ 分。 在样例 3 中，最优做法是移除第 2、3 根桅杆。此后你得到 $20$ 分，Gohu 得到 $9$ 分，差值为 $11$ 分。 ### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $23$ | 所有桅杆的 $x$ 坐标小于所有塔的 $x$ 坐标 | | $2$ | $10$ | $A, B, M \le 8$ | | $3$ | $22$ | $A, B, M \le 100$ | | $4$ | $45$ | 无额外限制 |