Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ phần tử ~(1 \le n \le 10^9)~ được mã hoá thành mảng ~b_1, b_2, \dots, b_m~ gồm ~m~ phần tử như sau:

Dãy ~b~ sẽ gồm các phần tử có dạng ~x.y~ với ý nghĩa: Phần tử hiện đang có giá trị là ~x, y~ phần tử tiếp theo lập thành một dãy cấp số cộng với công sai là 1. Xét ~a~ = {1, 2, 3, 2, 9, 4, 5, 6}. Ta có thể mã hóa mảng ~a~ thành mảng ~b~ = {1.3, 2.1, 9.1, 4.3} như sau:

Ví dụ: xét ~a = \{1, 2, 3, 2, 9, 4, 5, 6\}~. Ta có thể mã hoá dãy ~a~ thành ~b = \{1.3, 2.1, 9.1, 4.3\}~ như sau:

• Tại vị trí ~i = 1~, từ ~i = 1~ đến ~j = 3~ lập thành một cấp số cộng công sai ~1~, ~u_0 = 1~, gồm ~3~ phần tử ~\rightarrow~ ~b = \{1.3\}~.
• Tại vị trí ~i = 4~, từ ~i = 4~ đến ~j = 4~ lập thành một cấp số cộng công sai ~1~, ~u_0 = 2~, gồm ~1~ phần tử ~\rightarrow~ ~b = \{1.3, 2.1\}~.
• Tại vị trí ~i = 5~, từ ~i = 5~ đến ~j = 5~ lập thành một cấp số cộng công sai ~1~, ~u_0 = 9~, gồm ~1~ phần tử ~\rightarrow~ ~b = \{1.3, 2.1, 4.3\}~.~.
• Tại vị trí ~i = 6~, từ ~i = 6~ đến ~j = 8~ lập thành một cấp số cộng công sai ~1~, ~u_0 = 4~, gồm ~3~ phần tử ~\rightarrow~ ~b = \{1.3, 2.1, 9.1, 4.3\}~.

Sau khi mã hoá, dãy ~b~ sẽ gồm ~m~ phần tử ~(1 \le m \le 10^5)~.

Yêu cầu: Từ dãy ~b~ cho trước, hãy tìm độ dài của dãy con tăng dần dài nhất (LIS) của dãy ~a~ ban đầu (trước khi mã hoá).

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~m~, là số phần tử của dãy ~b_1, b_2, \dots, b_m~ ~(1 \le m \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x_i~ và ~y_i~ ~(1 \le x_i \le 10^6, 1 \le y_i \le 10^9, x_i + y_i \le 10^9)~.

Dữ liệu đầu vào đảm bảo tổng số phần tử của dãy ~a~ ban đầu không vượt quá ~10^9~.

Kết quả

• In ra một số nguyên duy nhất là độ dài của dãy con tăng dần dài nhất của dãy ~a~.

Sample Input 1

3
1 3
4 2
2 7

Sample Output 1

8

Sample Input 2

4
1 3
2 1
9 1
4 3

Sample Output 2

6

Chấm điểm

• Subtask 1 (5% số test): dãy ~a~ ban đầu có dạng ~a_i = a_{i-1} + 1~ (với mọi ~i~ thoả ~1 < i \le n~).
• Subtask 2 (10% số test): ~1 \le n \le 10^3~.
• Subtask 3 (15% số test): ~1 \le n \le 10^5~.
• Subtask 4 (25% số test): ~1 \le m \le 10^3~.
• Subtask 5 (45% số test): Không có ràng buộc gì thêm.