#题目描述

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

输出

50

样例 2

输入

2 1 100
6 5
100 4
5 100 2000

输出

9400

解释
先去 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

输出

2441

数据范围与提示

对于所有数据：

• $0 \leqslant p \leqslant 10^9$
• $0 < x_1 < x_2 < \dots < x_n \leqslant 10^9$
• $0 < a_i \leqslant 10^6$
• $0 < y_1 < y_2 < \dots < y_m \leqslant 10^9$
• $0 < b_j, c_j \leqslant 10^6$

子任务