题目描述

小杨管理着 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 次物资。

输出格式

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

样例

样例输入 1

3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000

样例输出 1

40186

样例解释

样例中，一种最优分配为：第 1 辆车使用站点 3，第 2 辆车使用站点 2，第 3 辆车使用站点 1，第 4 辆车使用站点 3。此时总行驶路程最短，为 40186。

数据范围

对于全部数据，保证 1≤n,m≤10^5，0<p_i<x，1≤c_i≤10^5，a_i,b_i 为非负整数，且所有站点容量之和不少于 m。