运送物资

题面描述

小杨管理着 $m$ 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 $n$ 个运输站点，这些站点位

于 A 市和 B 市之间。

每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的

位置可以视作数轴上的三个点，其中 A 市的坐标为 $0$，B 市的坐标为 $x$，运输站点的坐标为 $p$ 且有 $0<p<x$，货车每次去 A 市运送物资的总行驶路程为 $2p$，去 B 市运送物资的总行驶路程为 $2(x-p)$。

对于第 $i$ 个运输站点，其位置为 $p_i$ 且至多作为 $c_i$ 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运

输站点的情况下，所有货车每天的最短总行驶路程是多少。

输入格式

第一行包含三个正整数 $n,m,x$，代表运输站点数量，货车数量和两市距离。

之后 $n$ 行，每行包含两个正整数 $p_i,c_i$，代表第 $i$ 个运输站点的位置和最多容纳车辆数。

之后 $m$ 行，每行包含两个正整数 $a_i,b_i$，代表第 $i$ 辆货车每天需要向 A 市运送 $a_i$ 次物资，向 B 市运送 $b_i$ 次物资。

输出格式

输出一个正整数，代表所有货车每天的最短总行驶路程。

样例

13 4 1021 132 148 355 367 279 081 10000

140186

样例解释

第 $1$ 辆车的初始运输站点为站点 $3$，第 $2$ 辆车的初始运输站点为站点 $2$。第 $3$ 辆车的初始运输站点为站点 $1$，第 $4$ 辆车的初始运输站点为站点 $3$。此时总行驶路程最短，为 40186。

子任务编号	数据点占比	$n$	$m$	$c_i$
1	20%	$2$	$2$	$1$
2	20%	$\le10^5$	$\le10^5$	$1$
3	60%	$\le10^5$	$\le10^5$	$\le10^5$

对于全部数据，保证有 $1\le n,m\le10^5,2\le x\le10^8,0<p_i<x,1\le c_i\le10^5,0\le a_i,b_i\le10^5$。数据保证 $\sum c_i\ge m$。