프로그램 명: moving_table
제한시간: 1 초

ACM ( 유명한 컴퓨터 제조사 ) 회사는 아래 그림과 같이 생긴 빌딩의 한 층을 빌렸다..

이 층은 복도를 따라 남과 북으로 200 개의 방이 있다. 최근 이 회사는 시스템을 재 정비를 할려는 계획을 세웠다. 이 계획은 방사이에 많은 테이블을 옮겨야 하는 것을 포함하고 있다. 복도는 좁고 테이블이 커서 단지 하나의 테이블만 이 복도를 지날 수 있다.

이 작업을 하기위한 효율적인 계획이 필요하다.

매니저는 방에서 다른 방으로 테이블을 옮기는 데 소요되는 시간이 10 분 안이라는 것을 알았다. i 번째 방에서 j 번째 방으로 테이블을 옮길 때 i 번 방 앞의 복도와 j 번 방 앞의 복도가 사용된다. 그래서 , 매 10 분 동안 복도가 중첩되어 사용되지 않는다면 여러개의 작업을 동시에 할 수 있다.

아래 테이블은 가능한 경우 , 불가능한 경우의 예이다.

태이블 이동 이유
가능 30 번에서 50 번 방 과 60 번에서 90 번 방 복도를 공유하지 않음
11 번에서 12 번 방 과 14 번에서 13 번 방 복도를 공유하지 않음
불가능 20 번에서 40 번 방 과 31 번에서 80 번 방 31 번에서 40 번 방 앞 복도 공유
1 번에서 4 번 방 과 3 번에서 6 번 방 3 번 방 앞 복도 공유
2 번에서 8 번 방 과 7 번에서 10 번 방 7 번 방 앞 복도 공유

각 방에서 많아야 하나의 테이블이 들어가거나 나갈 것이다. 매니저는 모든 테이블을 옮기는 데 필요한 최소 시간을 구하는 방법을 찾고자 한다.

입력

첫 수는 이동 수 N ( 1 <= N <= 200 ) 이다. 다음 줄 N 줄은 각 각 두개의 양의 정수 s,t 가 입력으로 주어진다. s 방에서 t 방으로 의 이동을 의미한다. 방 번호는 많아야 한 번 입력데이터에 주어진다.

같은 방에서 같은 방으로 이동할 때도 복도를 사용하여야 한다.

출력

이동하는데 필요한 최소 분 수를 출력한다.

입출력 예

입력

4 
10 20 
30 40 
50 60 
70 80 

출력

10

입력

2 
1 3 
2 200 

출력

20

입력

3 
10 100 
20 80 
30 50 

출력

30

입력

3
1 1
2 2
3 3

출력

20
출처:Taejon 2001

[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]