Problem E
ICPC Team Generation

Vi is a coach for her university’s ICPC organization and is working on creating teams for their upcoming regional contest. They recently competed in the North America Qualifier and Vi is using the results as well as each person’s preferences to create as many teams of three as possible to send to regionals.

More specifically, $n$ people from Vi’s university competed in the North America Qualifier (NAQ), and each person got a unique rank from $1$ to $n$. The person at rank $r$ has two parameters, $a_ r$ and $b_ r$, where $a_ r \le r \le b_ r$, indicating that their two teammates must have a rank between $a_ r$ and $b_ r$, inclusive. Teams must have exactly three people.

Due to the collaborative environment, Vi notes that for every pair of individuals at ranks $i$ and $j$, if $i < j$, then $a_ i \le a_ j$ and $b_ i \le b_ j$.

Compute the maximum number of teams that Vi can send to regionals

Input

The first line of input contains a single integer $n$ ($3 \le n \le 50$), which is the number of competitors in the local contest.

Each of the next $n$ lines contains two integers $a_ r$ and $b_ r$ ($a_ r \le r \le b_ r$), where $r$ is the competitor’s rank. These are the limits of the ranks of the competitors that can be teamed with this competitor. The competitors are given in rank order, from $1$ to $n$. If $i < j$, then $a_ i \le a_ j$ and $b_ i \le b_ j$.

Output

Output a single integer, which is the maximum number of teams Vi can send to the regional contest.

6
1 2
1 2
2 5
2 6
2 6
5 6

1