별 모으기

각 스테이지는 보유 별이 충분할 때 최대 별 2개를 주며, 2N개의 별을 모두 모으는 최소 클리어 횟수를 구하거나 불가능하면 Too Bad를 출력한다.

보통6그리디정렬동적 계획법아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

앨리스는 최근에 나온 모바일 게임에 푹 빠져 있다. 이 게임은 스테이지 NN개로 이루어져 있고, 스테이지마다 별을 2개까지 모을 수 있다. 별을 모으는 일은 갈수록 어려워지므로, 이미 모은 별로 장비를 충분히 강화해야 어려운 스테이지에 도전할 수 있다.

규칙을 정확히 정리하면 다음과 같다. 아래에서 말하는 별의 개수는 그 스테이지를 클리어하기 직전에 앨리스가 모아 둔 별의 총 개수다.

  • 별을 하나도 얻지 못한 스테이지 ii를 별 aia_i개 이상 모은 상태에서 클리어하면, 그 스테이지에서 별 1개를 얻는다.
  • 별을 하나도 얻지 못한 스테이지 ii를 별 bib_i개 이상 모은 상태에서 클리어하면, 그 스테이지에서 별 2개를 얻는다.
  • 이미 별 1개를 얻은 스테이지 ii를 별 bib_i개 이상 모은 상태에서 클리어하면, 그 스테이지에서 남은 별 1개를 얻는다.

같은 스테이지를 여러 번 클리어해도 되지만, 한 스테이지에서 얻을 수 있는 별은 최대 2개다. 앨리스는 플레이 횟수를 최소로 줄이면서 별 2N2N개를 전부 모으려고 한다. 전부 모을 수 있는지 판단하고, 모을 수 있다면 스테이지를 클리어해야 하는 최소 횟수를 구하시오.

입력

첫째 줄에 스테이지의 개수 NN (1N10001 \le N \le 1000)이 주어진다.

다음 NN개 줄에 스테이지 ii의 정보인 두 정수 aia_ibib_i가 주어진다. (0aibi20010 \le a_i \le b_i \le 2001)

출력

앨리스가 별 2N2N개를 모두 모을 수 있으면 스테이지를 클리어하는 최소 횟수를 출력한다. 모두 모으는 것이 불가능하면 Too Bad를 출력한다.