시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB645425.000%

문제

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

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

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

입력

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

출력

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

예제 입력 1

3
100 60
100 140
120 180

예제 출력 1

79

예제 입력 2

1
0 200

예제 출력 2

199

예제 입력 3

2
100 60
120 140

예제 출력 3

82

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013