NOI 카니발

NOI 2011이 지린대학교에서 시작되었다. 전국의 뛰어난 정보올림피아드 참가자들을 맞이하기 위해 대학은 두 곳의 장소에서 카니발을 열기로 했다. 각 장소에는 여러 행사가 있고, 각 행사는 두 장소 중 한 곳에서만 열릴 수 있다.

카니발 기획자 앤디는 총 $n$개의 행사 신청서를 받았다. $i$번째 행사는 $S_i$에 시작해서 $T_i$ 단위 시간 동안 진행된다. 각 행사는 한 장소에서 열리거나, 아예 열리지 않을 수 있다.

두 장소에서 동시에 행사가 진행되면(행사가 시작하거나 끝나는 순간은 제외) 참가자들은 어느 장소에 갈지 고민하게 된다. 이를 막기 위해 두 장소에서 동시에 진행되는 행사가 있으면 안 된다. 같은 장소에서는 행사를 여러 개 열어도 된다.

행사가 적은 장소는 방문객이 적다. 앤디는 행사 수가 가장 적은 장소의 행사 수가 최대가 되도록 일정을 짜고 싶어 한다.

일부 행사는 특히 흥미로워서 앤디는 반드시 열고 싶어 한다. 각 행사 $i$에 대해, 그 행사를 두 장소 중 한 곳에서 반드시 연다는 조건에서 행사 수가 가장 적은 장소의 행사 수 최댓값을 구하라.

첫째 줄에 행사의 수 $n$이 주어진다. 이어지는 $n$개의 줄에는 각각 두 정수 $S_i$와 $T_i$가 주어진다. 이는 $i$번째 행사가 시각 $S_i$에 시작해서 $T_i$ 단위 시간 동안 진행된다는 뜻이다.

첫째 줄에는 추가 조건이 없을 때 행사 수가 가장 적은 장소의 행사 수 최댓값을 출력한다. 이어지는 $n$개의 줄에는 각각 $i$번째 행사를 반드시 열어야 한다는 조건에서, 행사 수가 가장 적은 장소의 행사 수 최댓값을 한 줄에 하나씩 출력한다.

$1 \le n \le 200$

$0 \le S_i \le 10^9$

$1 \le T_i \le 10^9$