You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time $300$ (measured in seconds after 5 am) and ends at time $1000$. The second farmer begins at time $700$ and ends at time $1200$. The third farmer begins at time $1500$ and ends at time $2100$. The longest continuous time during which at least one farmer was milking a cow was $900$ seconds (from $300$ to $1200$). The longest time no milking was done, between the beginning and the ending of all milking, was $300$ seconds ($1500$ minus $1200$).

Your job is to write a program that will examine a list of beginning and ending times for $N$ farmers ($1 \le N \le 5000$) milking $N$ cows and compute, in seconds:

• The longest time interval at least one cow was milked.
• The longest time interval after milking starts during which no cows were being milked.

Note: Milking from time $1$ through $10$, then from time $11$ through $20$ counts as two different time intervals.

输入格式

• Line 1: The single integer $N$.
• Lines 2..$N+1$: Two non-negative integers less than $1000000$, respectively the starting and ending time in seconds after 05:00.

输出格式

A single line with two integers that represent the longest continuous time of milking and the longest idle time.

3
300 1000
700 1200
1500 2100

900 300

提示

USACO Training Section $1.2$.