Có ~N~ hình chữ nhật, hình thứ ~i~ có chiều dài ~D_i~ và chiều rộng ~R_i~. Ta nói hình chữ nhật ~A~ lớn hơn hình chữ nhật ~B~ nếu diện tích của ~A~ lớn hơn diện tích của ~B~, hoặc hai diện tích bằng nhau nhưng chiều dài của ~A~ lớn hơn chiều dài của ~B~.

Yêu cầu

Chọn một dãy con theo đúng thứ tự ban đầu sao cho mỗi hình được chọn lớn hơn hình đứng ngay sau nó. Hãy tìm số lượng hình lớn nhất có thể chọn.

Input

Dòng đầu chứa số nguyên ~N~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~D_i,R_i~.

Output

In ra số lượng hình lớn nhất có thể chọn.

Subtask

• 70% số điểm: ~1 \le N \le 10^3~.
• 30% số điểm: ~1 \le N \le 10^5~, ~1 \le D_i,R_i \le 10^9~.

Ví dụ

4
2 3
3 2
2 2
1 3

3