题目背景

译自 ROI 2016 Day1 T3. Ловить или не ловить

题目描述

在卡马河上从事捕捞作业的渔船老板，决定在今年夏季对他们的业务进行优化。

他们获得了一份季节性捕鱼许可证，允许他们在河道上的 $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. $$

输出格式

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

3 2 0
1 5
2 3
4 5
2 2 10
3 6 5

50

2 1 100
6 5
100 4
5 100 2000

9400

3 3 10
1 1
10 100
20 10
2 1000 1
11 50 50
17 50 2

2441

提示

样例解释

在第二个样例中，最优策略如下：

• 船只先逆流航行至距离河口 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		$y_m < x_1$（即所有基地都在所有捕捞点的下游）	1
3	16		$x_n < y_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 完成