Tuyên và Quang chơi một trò chơi liên quan đến dãy số như sau:

Tuyên có ~k~ chiếc bút với màu mực khác nhau từ màu 1 đến màu ~k~. Tuyên viết ra giấy một dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Phần tử thứ ~i~ được viết bởi chiếc bút có màu mực ~b_i~ (~1 \le b_i \le k~; ~1 \le i \le n~).

Quang dùng bút xóa đi một số các phần tử của dãy ~a~ (cũng có thể không cần phải xóa phần tử nào) sao cho các phần tử còn lại chỉ được viết bằng một màu mực tạo thành một dãy con tăng dần dài nhất.

Yêu cầu: Hãy tìm độ dài của dãy con tăng dần dài nhất thỏa mãn điều kiện trên.

Input

• Dòng 1: Chứa hai số nguyên dương ~n, k~ (~n \le 10^5~; ~k \le 10~);
• Dòng thứ ~i~ trong ~n~ dòng sau chứa hai số nguyên dương ~a_i, b_i~ (~a_i \le 10^9~; ~1 \le b_i \le k~).

Output

• Ghi ra một số nguyên duy nhất là độ dài của dãy con dài nhất tìm được.

Sample Input 1

5 3
3 2
2 1
6 2
7 3
6 2

Sample Output 1

2