Độ dài dãy voi

Cho danh sách các con voi, mỗi con có cân nặng \(w\) và chỉ số IQ \(q\). Một nhóm voi được gọi là hợp lệ nếu có thể xếp chúng thành hàng sao cho cân nặng tăng ngặt và IQ giảm ngặt dọc theo hàng.

Tìm số lượng voi lớn nhất của một nhóm hợp lệ.

Input

• Mỗi dòng gồm hai số nguyên \(w\) và \(q\) của một con voi.
• Danh sách kết thúc bằng một dòng chứa số \(0\).

Output

In ra một số nguyên duy nhất: số con voi lớn nhất trong một nhóm hợp lệ.

Constraints

• Có tối đa \(10^5\) con voi (ít nhất một con).
• \(1 \le w, q \le 10^9\)
• Có thể có các con voi trùng cân nặng và/hoặc IQ.

Sample Input

3000 900
2000 1500
4500 700
2500 1400
5000 600
3500 1100
3500 1200
1000 2000
0

Sample Output

6

Explanation

Chọn \((1000,2000), (2000,1500), (2500,1400), (3000,900), (4500,700), (5000,600)\): cân nặng tăng ngặt, IQ giảm ngặt. Hai con \((3500, 1100)\) và \((3500,1200)\) cùng cân nặng nên không thể cùng xuất hiện, và không có nhóm nào đạt \(7\) con.