4316: [GESP202412六级] 运送物资
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## 题目背景
2024 年 12 月 GESP C++ 六级编程第 2 题
## 题目描述
小杨管理着 $m$ 辆货车，每辆货车每天需要向 $A$ 市和 $B$ 市运送若干次物资。小杨同时拥有 $n$ 个运输站点，这些站点位于 $A$ 市和 $B$ 市之间。
每次运送物资时，货车从初始运输站点出发，前往 $A$ 市或 $B$ 市，之后返回初始运输站点。$A$ 市、$B$ 市和运输站点的位置可以视作数轴上的三个点，其中 $A$ 市的坐标为 $0$，$B$ 市的坐标为 $x$，运输站点的坐标为 $p$ 且有 $0 \lt p \lt 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 10000样例输出 复制
40186提示
## 样例
```input1
3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000
```
```output1
40186
```
## 说明/提示
### 样例解释
第 $1$ 辆车的初始运输站点为站点 $3$，第 $2$ 辆车的初始运输站点为站点 $2$。第 $3$ 辆车的初始运输站点为站点 $1$，第 $4$ 辆车的初始运输站点为站点 $3$。此时总行驶路程最短，为 $40186$。
### 数据范围
| 子任务编号 | 数据点占比 | $n $ |$m $ |$c_i $ |
| ----------| ----------| -----------------|-----------------|-----------------|
| 1 | $ 20\%$ | $2$ | $ 2$ | $1$ |
| 2 | $20\%$ | $\leq 10^5$ | $ \leq 10^5$ | $1 $ |
| 3 | $60\%$ | $ \leq 10^5$ | $\leq 10^5 $ | $\leq 10^5$ |
对于全部数据，保证有 $1 \leq n,m \leq 10^5,2 \leq x \leq 10^8,0 \lt p_i \lt x, 1 \leq c_i \leq 10^5, 0 \leq a_i,b_i \leq 10^5$。数据保证 $\sum c_i \geq m$。