시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 1 1 100.000%

문제

아티스트 이동호는 자신의 그림을 창고에 보관해놓는다. 사실 아직 그림을 창고에 넣지는 않았고 앞으로 창고에 그림을 넣을 예정이다. 의 창고는 정사각형이고, 한 변이 200미터이다. 창고의 북쪽과 남쪽은 벽이다. 하지만, 서쪽과 동쪽은 전체가 미닫이문이다. 따라서, 다양한 크기의 트럭이 왔다 갔다 할 수 있다. 단, 모든 트럭의 너비는 정수미터이다. 안타깝게, 창고의 지붕은 기둥으로 지지되 있다. 또, 창고의 지붕은 너무 높아서 트럭이 지붕에 걸려서 못 들어가는 일은 없다.

아티스트 이동호는 최대한 큰 트럭, 즉, 너비가 되도록이면 큰 트럭을 창고를 통과시키려고 한다. (창고 속에서는 방향을 바꾸지 않는다.) 트럭은 서쪽에서 들어가서 동쪽으로 나온다.

창고에 있는 기둥의 위치가 입력으로 주어질 때, 창고를 통과할 수 있는 트럭의 크기의 최대값을 출력하는 프로그램을 작성하시오. 또, 기둥은 무시할 수 있는 크기를 가졌다. 트럭이 기둥이나 벽을 통과하거나 스치는 것은 허용되지 않는다.
 

입력

첫째 줄에 기둥의 개수 N이 주어진다. N은 300보다 작거나 같다. 둘째 줄부터 N개의 줄에 기둥의 위치가 주어진다. 기둥의 위치는 2개의 정수이고, 첫 번째 수는 동쪽 벽으로부터 떨어진 거리, 두 번째 수는 북쪽 벽으로부터 떨어진 거리이다. 이 수는 0보다 크거나 같고, 200보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력

3
100 60
100 140
120 180

예제 출력

79

힌트

출처