#214178. [PO Final 2022] 搭塔 / Legobyggartävlingen

你和你的宿敌 Gohu 参加了一场乐高搭建比赛。你们沿着 轴建造了许多高低不一、精致程度不同的塔，正等着评委到来。评分规则如下：如果你的某座塔的精致度为 ，高度为 （以乐高块计），那么你将为这座塔得到 分。配图对应样例 2。

::::align{center}

::::

这场比赛举世闻名，因此有许多无人机来回飞行拍摄这些漂亮的塔。为了避免无人机与塔相撞（从而把与其相撞的那一块及其上方的所有乐高块都撞掉），摄制组沿着 轴放置了许多高度各异的无线电桅杆。无人机每向前移动一格，可以向上或向下移动一格，并且总是尽量贴近地面飞行（以获得更好的画面），但绝不会低于任何桅杆的高度飞行。

突然，摄制组把目光移开了！你决定迅速移除一些桅杆，让无人机开始撞上这些塔。你应该移除哪些桅杆，才能使你的收益最大化（即你的得分减去 Gohu 的得分的差值最大）？

当无人机撞上某座塔时，这座塔的精致度不会降低，只有高度会降低。保证初始放置的桅杆使得无人机不会与任何塔相撞。

第一行包含三个整数 （）——你建造的塔的数量、Gohu 建造的塔的数量以及桅杆的数量。

接下来有 行，每行包含整数 （）——你的一座塔的 位置、精致度和高度。

然后有 行，每行包含整数 （）——Gohu 的一座塔的 位置、精致度和高度。

接着有 行，每行包含整数 （）——一根桅杆的 位置和高度。

任意两座塔不会有相同的 值，任意两根桅杆也不会有相同的 值；但桅杆可以与塔共享相同的 位置。

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

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

220

样例输入 3

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

样例输出 3

11

样例解释

::::align{center}

图 1：样例 1
::::

::::align{center}

图 2：样例 2
::::

::::align{center}

图 3：样例 3 ::::

在所有图片中，你的塔用蓝色表示，Gohu 的塔用红色表示。

在样例 1 中，最优做法是只移除第 1 根桅杆。此后你得到 分，Gohu 得到 分，差值为 分。

在样例 2 中，最优做法是移除第 2、3 根桅杆。此后你得到 分，Gohu 得到 分，差值为 分。

在样例 3 中，最优做法是移除第 2、3 根桅杆。此后你得到 分，Gohu 得到 分，差值为 分。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | | | 所有桅杆的 坐标小于所有塔的 坐标 | | | | | | | | | | | | 无额外限制 |