小杨管理着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次物资。
输出一个正整数，代表所有货车每天的最短总行驶路程。
3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 1000040186第1辆车的初始运输站点为站点3，第2辆车的初始运输站点为站点2，第3辆车的初始运输站点为站点1，第4辆车的初始运输站点为站点3。此时总行驶路程最短，为40186。
| 子任务编号 | 数据点占比 | n | m | c_i |
|---|---|---|---|---|
| 1 | 20% | 2 | 2 | 1 |
| 2 | 20% | ≤10^5 | ≤10^5 | 1 |
| 3 | 60% | ≤10^5 | ≤10^5 | ≤10^5 |
对于全部数据，保证有 $1 ≤ n,m ≤ 10^5, 2 ≤ x ≤ 10^8, 0 < p_i < x, 1 ≤ c_i ≤ 10^5, 0 ≤ a_i,b_i ≤ 10^5$。数据保证 $\sum c_i ≥ m$。