题目描述

你和你的宿敌 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 的得分）。

1 2 2
4 1 2
1 1 3
6 1 1
2 4
5 3

1

3 2 4
2 100 5
4 10 4
9 20 6
1 100 5
6 10 4
2 5
3 7
8 6
10 7

220

1 2 3
4 10 5
6 20 3
5 9 2
2 3
3 6
1 5

11

提示

样例解释

::::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$ | 无额外限制 |