Friendly Cities

Background

Special for beginners, ^_^

Problem Description

In the country of Palmia there is a big river running from east to west. The river has straight north and south banks, and each bank has $N$ cities at distinct positions. Every city on the north bank has exactly one friendly city on the south bank, and the friendly cities of different cities are all distinct.

Each pair of friendly cities applies to the government to open a straight shipping lane across the river connecting the two cities. However, because the fog on the river is too thick, the government decides to avoid any two lanes crossing each other, in order to prevent accidents. Write a program to help the government approve and reject applications so that, while no two lanes intersect, the number of approved applications is as large as possible.

Input Format

The first line is an integer $N$ ($1 \le N \le 5000$), the number of cities.

Lines $2$ to $N+1$ each contain two integers separated by a space, denoting the coordinates of a pair of friendly cities on the south and north banks ($0 \le x_i \le 10000$).

Output Format

Output a single line with one integer: the maximum number of applications the government can approve.

Sample Input 1

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

Sample Output 1

4

Constraints

1s, 1024KiB for each test case.