Description

Three farmers get up at $5$ a.m. every morning and go to the barn to milk three cows.

The first farmer starts milking at $300$ seconds (counted from $5$ o'clock) and continues until $1000$ seconds. The second farmer starts at $700$ seconds and ends at $1200$ seconds. The third farmer starts at $1500$ seconds and ends at $2100$ seconds.

The longest continuous time during which at least one farmer is milking is $900$ seconds (from $300$ seconds to $1200$ seconds), and the longest continuous time during which no one is milking (from the beginning of any milking to the end of all milking) is $300$ seconds (from $1200$ seconds to $1500$ seconds).

Your task is to write a program that reads a list of working times for $n$ farmers milking $n$ cows and computes the following two values (both in seconds):

1. The longest interval during which at least one person is milking.
2. The longest interval during which no one is milking (counted from when milking begins).

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain two non-negative integers $l, r$, representing one farmer’s start time and end time.

Output Format

Output a single line with two integers separated by a single space: the two answers required by the problem.

3
300 1000
700 1200
1500 2100

900 300

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 5000$, $0 \le l \le r \le 10^6$.

Problem translation from NOCOW.

USACO Training Section $1.2$.

Translated by ChatGPT 5