P14207 [ROI 2016 Day1] 捕捞，还是不捕捞？

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day1 T3.** ***[Ловить или не ловить](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day1.pdf)***

在卡马河上从事捕捞作业的渔船老板，决定在今年夏季对他们的业务进行优化。 他们获得了一份季节性捕鱼许可证，允许他们在河道上的 $n$ 个指定点进行捕捞，这些点分别位于距离河口 $x_1, x_2, \ldots, x_n$ 公里的位置。在第 $i$ 个捕捞点，最多可以捕捞 $a_i$ 吨鱼。 捕获的鱼可以在沿河分布的 $m$ 个批发基地出售，这些基地分别位于距离河口 $y_1, y_2, \ldots, y_m$ 公里的位置。其中，第 $j$ 个基地在本季最多可以购买 $b_j$ 吨鱼，并且以每吨 $c_j$ 卢布的价格收购。从河口到捕捞点和批发基地的距离均沿着河道方向测量。 渔船从河口出发，并在季末返回河口。在整个季节中，渔船可以任意在河道上向上游或下游航行，并可在任意位置停下进行捕捞或销售。渔船的载重能力足够大，可以运输任意数量的鱼。当渔船从河口向上游$ $行驶（逆流而上）时，每行驶 $1$ 公里需要消耗价值 $p$ 卢布的燃料；当渔船向下游$ $行驶（顺流而下）时，则不消耗燃料。 季末时的利润定义为出售鱼的总收入减去燃料的总花费。请编写一个程序，计算在该季节中可以获得的最大利润。

第一行包含三个整数 $n$, $m$, $p$——分别表示捕捞点的数量、批发基地的数量，以及燃料单价。满足约束：$1 \le n, m \le 500\,000$；$0 \le p \le 10^9$。 接下来的 $n$ 行中，每行包含两个整数 $x_i, a_i$，表示捕捞点距离河口的距离，以及该点可捕捞的最大鱼量： $$ 0 < x_1 < x_2 < \ldots < x_n \le 10^9, \quad 0 < a_i \le 10^6. $$ 接下来的 $m$ 行中，每行包含三个整数 $y_j, b_j, c_j$，表示批发基地距离河口的距离、该基地最多可收购的鱼量以及每吨鱼的收购价： $$ 0 < y_1 < y_2 < \ldots < y_m \le 10^9, \quad 0 < b_j, c_j \le 10^6. $$

输出一个整数——即最大可能获得的利润。

### 样例解释 在第二个样例中，最优策略如下： - 船只先逆流航行至距离河口 6 公里的捕捞点，燃料消耗为 $6 \times 100 = 600$ 卢布，在此捕捞 5 吨鱼。 - 然后顺流航行 1 公里，到距离河口 5 公里的批发基地出售所有 5 吨鱼，每吨售价为 2000 卢布。 - 最后返回河口。总利润为 $5 \times 2000 - 600 = 9400$ 卢布。 ### 数据范围 | 子任务编号 | 分值 | $n, m$ | 附加条件 | 必须通过的子任务 | |:-----------:|:----:|:-------:|:----------:|:----------------:| | 1 | 16 | $1 \le n, m \le 50\,000$ | $p = 0$ | | | 2 | 9 | $1 \le n, m \le 50\,000$ | $y_m < x_1$（即所有基地都在所有捕捞点的下游） | 1 | | 3 | 16 | $1 \le n, m \le 50\,000$ | $x_n < y_1$（即所有捕捞点都在所有基地的下游） | 1 | | 4 | 11 | $1 \le n, m \le 1\,000$ | 无额外条件 | | | 5 | 9 | $1 \le n, m \le 6\,000$ | 无额外条件 | 4 | | 6 | 20 | $1 \le n, m \le 50\,000$ | 无额外条件 | 1–5 | | 7 | 6 | $1 \le n, m \le 200\,000$ | 无额外条件 | 1–6 | | 8 | 7 | $1 \le n, m \le 320\,000$ | 无额外条件 | 1–7 | | 9 | 6 | $1 \le n, m \le 500\,000$ | 无额外条件 | 1–8 | 翻译由 ChatGPT-5 完成