ICPC 팀 구성

시간 제한1초메모리 제한1024 MB

요약

각 참가자가 순위 a에서 b 사이의 사람을 팀원으로 고를 수 있을 때, 셋이 한 팀을 이루는 최대 팀 수를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구간
정답자: 아직 제출이 없습니다

문제

Vi는 대학교 ICPC 조직의 코치이다. 그녀는 다가오는 지역 예선에 보낼 팀을 구성하는 중이다. 대학교는 최근 North America Qualifier(NAQ)에 참가했고, Vi는 그 결과와 각 참가자의 선호를 바탕으로 지역 예선에 보낼 3인 팀을 가능한 한 많이 만든다.

대학교에서 NAQ에 참가한 사람은 $n$ 명이다. 각 참가자는 1부터 $n$ 까지 서로 다른 순위를 받았다. 순위가 $r$ 인 참가자는 $a_r$ 과 $b_r$ 이라는 두 매개변수를 가지며, $a_r \le r \le b_r$ 이다. 이 참가자의 두 팀원은 순위가 $a_r$ 이상 $b_r$ 이하여야 한다. 팀은 정확히 3명으로 구성된다.

협업 환경이므로, 순위가 $i$ 와 $j$ 인 참가자 쌍에 대해 $i < j$ 이면 $a_i \le a_j$ 이고 $b_i \le b_j$ 이다.

Vi가 지역 예선에 보낼 수 있는 팀 수의 최댓값을 구하시오.

입력

첫 줄에 지역 대회의 참가자 수를 나타내는 정수 $n$ ( $3 \le n \le 50$ )이 주어진다.

다음 $n$ 개 줄에는 각각 두 정수 $a_r$ 과 $b_r$ ( $a_r \le r \le b_r$ )이 주어진다. 여기서 $r$ 은 해당 참가자의 순위이다. 이 값은 해당 참가자의 팀원 순위 범위의 하한과 상한이다. 참가자는 순위 1부터 $n$ 까지의 순서로 주어진다. $i < j$ 이면 $a_i \le a_j$ 이고 $b_i \le b_j$ 이다.

출력

Vi가 지역 예선에 보낼 수 있는 팀 수의 최댓값을 나타내는 정수 하나를 출력한다.

예제1

예제 1
입력
```
6
1 2
1 2
2 5
2 6
2 6
5 6
```
예상 출력
```
1
```