运送物资

题目描述

⼩杨管理着 辆货车，每辆货车每天需要向 A 市和 B 市运送若⼲次物资。⼩杨同时拥有 个运输站点，这些站点位 于 A 市和 B 市之间。 每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的 位置可以视作数轴上的三个点，其中 A 市的坐标为 ，B 市的坐标为 ，运输站点的坐标为 且有 ，货车 每次去 A 市运送物资的总⾏驶路程为 ，去 B 市运送物资的总⾏驶路程为 。 对于第 个运输站点，其位置为 且⾄多作为 辆车的初始运输站点。⼩杨想知道，在最优分配每辆货车的初始运 输站点的情况下，所有货车每天的最短总⾏驶路程是多少。

输入格式

第⼀⾏包含三个正整数 ，代表运输站点数量，货车数量和两市距离。 之后 ⾏，每⾏包含两个正整数 ，代表第 个运输站点的位置和最多容纳车辆数。 之后 ⾏，每⾏包含两个正整数 ，代表第 辆货车每天需要向 A 市运送 次物资，向 B 市运送 次物资。

输出格式

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

样例输入 #1

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

样例输出 #1

样例解释 #1

第 辆车的初始运输站点为站点 ，第 辆车的初始运输站点为站点 。第 辆车的初始运输站点为站点 ，第 辆 车的初始运输站点为站点 。此时总⾏驶路程最短，为 40186。 子任务编号 数据点占比 1 20% 2 20% 3 60% 对于全部数据，保证有 。数据保证 。

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。