#8827. 「一本通 5.6 例 4」Cats Transport
「一本通 5.6 例 4」Cats Transport
题目描述
原题来自:Codeforces Round #185 (Div. 1) B.
小 S 是农场主,他养了 只猫,雇了 位饲养员。农场中有一条笔直的路,路边有 座山,从 到 编号。第 座山与第 座山之间的距离是 。饲养员都住在 号山上。
有一天,猫出去玩。第 只猫去 号山玩,玩到时刻 停止,然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从 号山走到 号山,把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间,速度为 米每单位时间。饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。
例如有两座相距为 的山,一只猫在 号山玩,玩到时刻 开始等待。如果饲养员从 号山在时刻 或 出发,那么他可以接到猫,猫的等待时间为 或 。而如果他于时刻 出发,那么他将于时刻 经过 号山,不能接到当时仍在玩的猫。
你的任务是规划每个饲养员从 号山出发的时间,使得所有猫等待时间的总和尽量小。饲养员出发的时间可以为负。
输入格式
第一行三个整数 ;
第二行 个正整数 ,表示第 座山与第 座山之间的距离是 ;
接下去 行每行两个整数 。
输出格式
输出一个整数表示答案。
样例
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
3
数据范围与提示
对于全部数据,$2\le N\le 10^5,1\le M\le 10^5,1\le p\le 100,1\le D_i\lt 10^4,1\le H_i\le N,0\le T_i\le 10^9$。