Informatica Online Judge

  Milking Cows (우유짜기) [0253 / 00FD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 109   Total Tried : 135


The Champion of this Problem (C++) : gs18103 - ms / 580byte
My Best Submission (C++) : N/A

[]

Background

매일아침 3명의 농부가 일어나 젖소 3마리의 젖을 짜기 위해 외양간으로 향한다. 첫번째 농부는 시간 300에(아침 5시 이후에 측정하기 시작한 시간으로) 그의 젖소의 젖을 짜기 시작해 시간 1000에 끝낸다. 두번 째 농부는 시간 700에 시작해서 시간 1200에 끝낸다.

세번째 농부는 시간 1500에 시작해서 2100에 끝낸다. 적어도 한명 이상의 농부가 가장 오랜 동안 계속해서 젖을 짤 수 있는 시간은 900초이다(300초에서 1200초까지 세명의 농부가 같이 일한다.. 역자 주: 간트 도표를 그려볼 것). 젖을 짜기 시작해 끝내는 동안, 젖을 짜지 않는 가장 긴시간은 300 초였다.
(1500 빼기 1200 역자 주: 마찬가지 간트 도표를 보면 확실하게 보인다.)

여러분의 일은 N명의(1<=N<=5000) 농부가 N마리의 젖소의 젖을 짜는데 걸리는 시작시간과 종료시간을 계산하는 프로그램을 작성하고, 아래의 시간을 계산(초단위로) 하여라:


-적어도 한 마리 이상의 젖소의 젖을 짜고 있는 가장 긴시간.

-(젖을 짜기 시작한 이후로) 어떤 소도 젖을 짜지 않고 있는 가장 긴 시간.

Input

첫 번째 줄에 하나의 정수 N이 주어지고 두번째 줄에서 N+1번째 줄까지 0이상 1,000,000이하의 정수, 500초 이후의 초단위의 시작 시각과 종료시각이 주어진다.

Output

우유짜는 가장 긴 시간과 우유를 짜지 않은 가장 긴 시간을 공백으로 구분하여 출력하라.

IO Example

입력
3
300 1000
700 1200
1500 2100

출력
900 300

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]