#3062. 「ROI 2016 Day1」摸鱼否

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

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

河口是入海口啊,你说河口在上游还是下游 →_→
「开渔」指捕鱼季开始,「休渔」指捕鱼季结束

开渔了!你可以在河流上的 n 个地点捕鱼,它们距离河口的距离为 x_1\ldots x_n (按递增顺序给出)。在这个捕鱼季节, i 号地点最多能捕捞 a_i 吨鱼。
你可以在岸边的 m 个批发基地卖鱼, y_1\ldots y_m (按递增顺序给出)。在这个捕鱼季节, j 号批发基地计划以每吨 c_j 卢布的价格购买至多 b_j 吨鱼。
开渔时,你从河口出发捕鱼,休渔时需要返回河口。你可以任意顺流而下 / 逆流而上 / 捕鱼 / 卖鱼。逆流而上的燃料费用为每单位距离 p 卢布,顺流而下则无需燃料费用。
试求可以获得的最大利润(卖鱼所得的净利润与消耗燃料的成本之差)。

输入格式

n,m,p
接下来 n 行: x_i, a_i
接下来 m 行: y_j, b_j, c_j

样例

样例输入 1

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

样例输出 1

50

样例输入 2

2 1 100
6 5
100 4
5 100 2000

样例输出 2

9400

样例说明 2

  • 先去 1 号地点(消耗了价值 600 卢布的燃料)
  • 捕捞 5 吨鱼
  • 顺流而下 1 单位距离,到达 1 号批发基地
  • 以每吨 2000 卢布的价格卖掉(毛收入 10000 卢布)

总利润 9400 卢布。

样例输入 3

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

样例输出 3

2441

数据范围与提示

对于所有数据, 0 ⩽ p ⩽ 10^9, 0 < x_1 < x_2 < \dots < x_n ⩽ 10^9, 0 < a_i ⩽ 10^6, 0 < y_1 < y_2 < \dots < y_m ⩽ 10^9, 0 < b_j ,c_j ⩽ 10 ^6.

子任务 # 分值 1 ⩽ n,m ⩽ 附加条件 依赖子任务
1 16 \phantom{0}50\:000 p = 0
2 9 y_m < x_1 1
3 16 x_n < y_1  1 
4 11 \phantom{00}1\:000
5 9 \phantom{00}8\:500 4
6 20 \phantom{0}50\:000 1–5
7 6 200\:000 1–6
8 7 320\:000 1–7
9 6 500\:000 1–8