题目描述

译自 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

input

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

output

50

样例 2

input

2 1 100
6 5
100 4
5 100 2000

output

9400

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

总利润 9400 卢布。

样例 3

input

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

output

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.$