Description

Two PACMAN eat beans. At the beginning, both PACMAN are to the lower-left of the origin, and all beans are to the upper-right. A PACMAN eats a bean when it reaches its location. The PACMAN move in a strange way: they can only move right or up. Their paths may have intersection points but cannot cross each other. Please help the two PACMAN compute the maximum total number of beans they can eat together.

Input Format

The first line contains an integer $N$, denoting the number of beans. The next $N$ lines each contain a pair of positive integers, representing the coordinates of the $i$-th bean. The coordinates of any two beans are distinct.

Output Format

Output a single line containing one integer: the maximum total number of beans the two PACMAN can eat.

8 
8 1 
1 5
5 7 
2 2 
7 8 
4 6 
3 3 
6 4

7

Hint

For 100% of the testdata, $N \leq 2000$.

Translated by ChatGPT 5