小杨管理着辆货车，每辆货车每天需要向A市和B市运送若干次物资。小杨同时拥有个运输站点，这些站点位于A市和B市之间。
每次运送物资时，货车从初始运输站点出发，前往A市或B市，之后返回初始运输站点。A市、B市和运输站点的位置可以视作数轴上的三个点，其中A市的坐标为0，B市的坐标为，运输站点的坐标为且有 ，货车每次去A市运送物资的总行驶路程为，去B市运送物资的总行驶路程为。
对于第个运输站点，其位置为且至多作为辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
第一行包含三个正整数，代表运输站点数量、货车数量和两市距离。
之后行，每行包含两个正整数，代表第个运输站点的位置和最多容纳车辆数。
之后行，每行包含两个正整数，代表第辆货车每天需要向A市运送次物资，向B市运送次物资。
输出一个正整数，代表所有货车每天的最短总行驶路程。
输入：
3 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000
输出：
40186
第1辆车的初始运输站点为站点3，第2辆车的初始运输站点为站点2。第3辆车的初始运输站点为站点1，第4辆车的初始运输站点为站点3。此时总行驶路程最短，为40186。
对于全部数据，保证有 。
数据保证。
1.0 s
512.0 MB