The Render Farm

A cloud rendering service has N frames to render. Each frame i takes D[i] minutes to render and has a deadline L[i] (minutes from now). You start at time 0 and render frames one by one. The 'lateness' of a frame is max(0, completion_time - deadline). Your goal is to minimize the MAXIMUM lateness among all frames. Input Format: The first line contains N. The next N lines each contain D[i] and L[i]. Output Format: A single integer representing the minimum possible maximum lateness. Example: Input: 2 10 15 5 10 Output: 5 Explanation: Render frame 2 first (finishes at 5, deadline 10, lateness 0), then frame 1 (finishes at 15, deadline 15, lateness 0). Max lateness 0. If frame 1 first, finishes at 10, then frame 2 finishes at 15 (deadline 10, lateness 5). Max lateness 5. Wait, in this example, EDF gives 0.