10564 - Homework Arrangement   

Description

身在資工系的小傑,學期中常有寫不完的作業,每份作業都有繳交期限。認真的小傑對課業成績非常在意,總是盡力完成所有作業,可是到了期中他發現,就算不吃飯、不上課、不睡覺,也無法在期限內完成所有作業,於是他必須採取棄保策略,他已經預算好每個作業所要花的時間,請你算出他最多能交出幾份作業。

舉例來說,如範例一,小傑可以在時間0 ~ 2完成作業一,時間2 ~ 3完成作業二,此時就無法完成作業三,因為它的期限是在時間4,如圖 (a) 所示;另一種策略是:時間0 ~ 2完成作業一,時間2 ~ 4完成作業三,如圖 (b) 所示。

 
 
圖 (a) 



 
圖 (b)

Input

第1行輸入一個正整數 n,代表作業份數

第2 ~ n + 1行,每行兩個正整數,分別表示這個作業的繳交期限和完成它所需的時間,單位皆為一小時,可以假設小傑能從時間 0 開始不眠不休拼命地趕作業。
限制:n ≤ 1,000,000,所有整數皆可存於32-bit signed integer (ex: int in C++)
 

Output

輸出一個整數代表最多能完成的作業份數。(剛好在作業繳交期限時間點寫完的作業算是完成的)

Sample Input  Download

Sample Output  Download

Tags




Discuss