‹ 上一题 下一题 ›

s09149. 注定迟到 未做

1000 ms 256 MB 测试点 10 通过率 17% S-06·贪心进阶与反悔贪心优先队列贪心

题目描述

项作业排在同一台机器上加工,机器从时刻 开始工作,同一时刻只能加工一项作业,加工一旦开始不可中断。作业 需要连续加工 分钟,截止时刻为 :设它的完成时刻为 ,当 时称它不迟到。

加工顺序可以自由选择。若存在使全部作业都不迟到的顺序,第一行输出 YES,否则输出 NO。

第二行输出:在所有加工顺序中, 的最小值。由定义,当且仅当第一行为 YES 时该值为 ;NO 时它就是「注定迟到」之下最小的最大超时分钟数。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 。

输出格式

两行:第一行 YES 或 NO;第二行一个整数,含义如上。

样例 1

样例

输入
3
3 5
2 4
4 9
输出
YES
0

按截止时刻升序加工:、、,全部赶上,最大超时为 。

样例 2

任何顺序下两作业总时长都是 ,末项完成于 :先做前者则后者 超时 ,反之 超时 ,故最小最大超时为 。

数据范围

;。答案可能超过 位整数范围。

输入
输出

            
答案