806 . 觀光行程
Description
本題改編自 2021 年 1 月 APCS 考古題。
豆島是一個觀光導遊兼顧問，主要負責為旅行社安排行程。為了讓行程看起來緊湊有效率，豆導希望無論如何都只往東北方走，以避免看起來像在往回頭路的方向走。
如果將當前位置座標定在 $(0,0)$，且正 $y$ 軸方向為北方。給定 $N$ 個位於座標 $(x,y)$ 上的景點，豆導希望規劃一條路線使得經過的景點 $x$ 座標總是不比前一個小，$y$ 座標也不比前一個小。
想請問你，基於 $N$ 座城市位置和豆導的堅持下，一個行程最多能包含多少景點。
Input Format
輸入第一行是一整數 $N$，代表城市數量。
接下來 $N$ 行是兩個空白分隔的整數 $x,y$，代表景點的座標。
對於 $20\%$ 的輸入，保證 $1\le n,x,y\le 100$。
對於 $30\%$ 的輸入，保證 $1\le n\le 1000$，$1\le x,y\le 10^ 7$。
對於 $50\%$ 的輸入，保證 $1\le n\le 200000$，$1\le x,y\le 10^ 7$。
輸入保證沒有兩個景點位置完全相同。
Output Format
輸出一行一個整數，代表最多可以拜訪的景點。
Sample Input 1
3
1 1
2 7
3 1
1 1
2 7
3 1
Sample Output 1
2
Sample Input 2
5
1 2
2 2
2 3
3 3
3 4
1 2
2 2
2 3
3 3
3 4
Sample Output 2
5
Hints
Problem Source
APCS 歷屆
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~8 | $1\le n,x,y\le 100$ | 20 |
| 3 | 0~12 | $1\le n\le 1000, 1\le x,y\le 10^ 7$ | 30 |
| 4 | 0~24 | 無額外限制 | 50 |