题目描述
一台打印机从时刻 开始工作,同一时刻只能打印一份文档,打印一旦开始不可中断。第 份文档在时刻 到达,需要连续打印 分钟。
打印顺序遵循最短作业优先:每当打印机空闲时,在所有已到达且未打印的文档中,选 最小的一份开始打印;若有多份 相同,选 最小的;仍相同则选输入顺序靠前的。若打印机空闲时还没有文档到达,时间直接跳到下一份文档的到达时刻。
第 份文档的等待时长定义为它的开始打印时刻减去 。请按上述规程模拟,输出全部文档等待时长之和。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 。
输出格式
一行一个整数,表示全部文档等待时长之和。
样例 1
样例
输入
4 0 7 2 4 3 1 6 2
输出
14
时刻 只有一份文档可打,打印至 ;此时三份文档已到达,选时长 的(等待 ),再选时长 的(等待 ),最后选时长 的(等待 ),总等待 。
样例 2
输入
3 0 10 12 1 12 5
输出
1
第一份打印到 ,打印机空闲且下一批文档 才到达,时间跳到 ;先打时长 的,另一份从 等起,等待 。
数据范围
;;。答案可能超过 位整数的表示范围,数据保证答案在 位整数范围内。