위험한 탑
시간 제한2초메모리 제한512 MB
각 블록은 1 × Ai × Bi 크기이고 Ai 또는 Bi를 높이로 삼아 놓을 수 있으며, 위에 놓인 블록은 아래 블록보다 가로 길이가 짧아야 합니다. 탑 높이의 최댓값을 구합니다.
문제
ICPC에서 좋은 성적을 내려면 수행이 필요하다. 토끼는 ICPC에서 이기고 싶어서 오늘도 수행을 하기로 했다.
오늘의 수행은 나무 블록을 정성껏 쌓아 올려서, 절대 오타를 내지 않을 만큼 손끝이 능숙해지는 것이다. 블록이 많이 있으니 높은 탑을 만들어 보자.
블록은 N개 있고, i번째 (1 ≤ i ≤ N) 블록은 1 × A**i × B**i 크기의 직육면체 모양이다. 길이가 1인 모서리는 깊이 방향으로 쓰고, 길이가 A**i, B**i인 모서리는 각각 가로 방향과 높이 방향에 하나씩 배정하기로 했다. 블록을 쌓을 때, 위층 블록은 아래층 블록보다 가로 길이가 엄격하게 짧아야 한다. 블록은 원하는 순서로 쓸 수 있고, 쓰지 않는 블록이 있어도 된다. 이런 제약 아래에서 만들 수 있는 가장 높은 탑을 만들고 싶다.
입력
N
A1 B1
...
AN BN
1 ≤ N ≤ 1,000, 1 ≤ A**i, B**i ≤ 1,000,000을 만족한다. 입력의 값은 모두 정수이다.
출력
탑 높이의 최댓값을 1행에 출력하라.