#G1086. [GESP202412 六级] 运送物资

[GESP202412 六级] 运送物资

[GESP202412 六级] 运送物资

题目描述

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

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

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

输入格式

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

之后 nn 行,每行包含两个正整数 pi,cip_i, c_i,代表第 ii 个运输站点的位置和最多容纳车辆数。

之后 mm 行,每行包含两个正整数 ai,bia_i, b_i,代表第 ii 辆货车每天需要向 A 市运送 aia_i 次物资,向 B 市运送 bib_i 次物资。

输出格式

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

样例 #1

样例输入 #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。

数据范围

子任务编号 数据点占比 nn mm cic_i
1 20% =2= 2 =1= 1
2 ≤105≤ 10^5
3 60% ≤105≤ 10^5
  • 对于全部数据,保证有 1≤n,m≤1051 ≤ n, m ≤ 10^5,2≤x≤1082 ≤ x ≤ 10^8,0<pi<x0 < p_i < x,1≤ci≤1051 ≤ c_i ≤ 10^5,0≤ai,bi≤1050 ≤ a_i, b_i ≤ 10^5。数据保证 ∑ci≥m\sum c_i ≥ m。