运送物资

时间限制：2.0 s    内存限制：512.0 MB

题目描述

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

    每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 ，B 市的坐标为 ，运输站点的坐标为p且有 0<p<x，货车每次去 A 市运送物资的总行驶路程为 2p，去 B 市运送物资的总行驶路程为 2(x-p)。

    对于第i个运输站点，其位置为 pⁱ 且至多作为 cⁱ 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。

输入格式

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

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

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

输出格式

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

输入样例

3 4 10

1 1

2 1

8 3

5 3

7 2

9 0

1 10000

输出样例

40186

样例解释

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