F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 1930. -- [Shoi2003]pacman 吃豆豆

1930: [Shoi2003]pacman 吃豆豆

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 2665  Solved: 645
[Submit][Status][Discuss]

Description

两个PACMAN吃豆豆。一开始的时候,PACMAN都在坐标原点的左下方,豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪,只能向右走或者向上走,他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下,他们俩加起来最多能吃掉多少豆豆。

Input

第一行为一个整数N,表示豆豆的数目。 接下来 N 行,每行一对正整数,表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。

Output

仅有一行包含一个整数,即两个PACMAN加起来最多能吃掉的豆豆数量

Sample Input

8

8 1

1 5

5 7

2 2

7 8

4 6

3 3

6 4

Sample Output

7

HINT



N < = 2000

Source

[Submit][Status][Discuss]

HOME Back