Joke with Turtles

Time limit2sMemory limit128 MB

Summary

Each turtle claims a count of turtles ahead and behind it; choose positions to maximize how many claims hold at once.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Sorting, Intervals
Solved: No attempts yet

Problem

There is a famous riddle-joke for children:

Three turtles are crawling along a road. The first turtle says: "There are two turtles ahead of me." The second turtle says: "There are two turtles behind me." The third turtle says: "There are two turtles ahead of me and two turtles behind me." How can this be?

The answer is: the third turtle is lying!

In this problem, $n$ turtles are crawling along a road. Several turtles may crawl together in a group at the same position, so that turtles in the same group see none of their group members either ahead or behind them. Each turtle makes a statement of the form: "There are $a_i$ turtles ahead of me and $b_i$ turtles behind me." Find the minimum possible number of turtles that are lying.

Formally, turtle $i$ has a coordinate $x_i$ , and different turtles may share the same coordinate. Turtle $i$ tells the truth if and only if the number of turtles $j$ with $x_j > x_i$ is exactly $a_i$ and the number of turtles $j$ with $x_j < x_i$ is exactly $b_i$ ; otherwise turtle $i$ is lying. You may choose the coordinates freely, and you must report the minimum number of turtles that must be lying, taken over all arrangements (equivalently, $n$ minus the maximum number that can simultaneously tell the truth).

Input

The first line contains an integer $n$ ( $1 \le n \le 1000$ ). Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ( $0 \le a_i, b_i \le 1000$ ) describing the statement of turtle $i$ for $i$ from $1$ to $n$ .

Output

Print a single integer $m$ : the minimum number of turtles that must be lying.

Examples2

Example 1
Input
```
3
2 0
0 2
2 2
```
Expected output
```
1
```
Example 2
Input
```
5
0 2
0 3
2 1
1 2
4 0
```
Expected output
```
2
```