题目描述
文印店有一台打印机,从时刻 开始工作。今有 个打印任务,任务 在时刻 到达,需要连续打印 秒。打印机同一时刻只能打印一个任务,打印一旦开始不可中断。
关于先打印哪个任务,同学们有两种主张:先来先做,或最短优先。本题统一采用最短优先口径:每当打印机空闲时,在所有已到达且未完成的任务中,选择所需时间 最小的一个;若这样的任务有多个,选择输入序号最小的一个。打印机空闲且没有已到达的任务时,时间直接跳到下一个任务的到达时刻。
一个任务的等待时长 = 它的开始打印时刻 − 它的到达时刻。求按最短优先口径执行时,全部任务的总等待时长。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 ,含义如上。
输出格式
一行一个整数:总等待时长。
样例 1
样例
输入
4 0 7 2 4 3 1 6 2
输出
14
时刻 只有任务 ,先做任务 ( 到 );时刻 时任务 都已到达,最短的是任务 ( 到 );再是任务 ( 到 );最后任务 ( 到 )。等待 。
样例 2
输入
3 0 5 0 3 1 3
输出
8
先做任务 (最短,序号平局取小),再任务 ,最后任务 ;等待 。若按先来先做口径,答案为 ——两种口径在这里给出不同结果。
数据范围
;;。答案可能超过 位整数范围。