Đàn bò lại ra ngoài vận động móng guốc! Có \(N\) cô bò đang chạy bộ trên một đường chạy một làn dài vô hạn (\(1 \le N \le 100\,000\)). Mỗi cô bò xuất phát tại một vị trí khác nhau trên đường chạy, và một số cô bò chạy với tốc độ khác nhau.

Vì đường chạy chỉ có một làn, các cô bò không thể vượt nhau. Khi một cô bò nhanh hơn bắt kịp một cô bò khác, cô phải chạy chậm lại để tránh đâm vào cô bò phía trước và trở thành một thành viên của cùng nhóm chạy.

Các cô bò sẽ chạy trong \(T\) phút (\(1 \le T \le 1\,000\,000\,000\)). Hãy giúp Farmer John xác định còn lại bao nhiêu nhóm tại thời điểm đó. Hai cô bò được xem là thuộc cùng một nhóm nếu chúng ở cùng vị trí sau khi kết thúc \(T\) phút.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(T\).

\(N\) dòng tiếp theo, mỗi dòng chứa vị trí ban đầu và tốc độ của một cô bò. Vị trí là một số nguyên không âm, còn tốc độ là một số nguyên dương; cả hai số đều không vượt quá 1 tỷ. Tất cả các cô bò xuất phát tại những vị trí khác nhau, và các vị trí này được cho theo thứ tự tăng dần trong dữ liệu vào.

Dữ liệu ra

In ra một số nguyên duy nhất cho biết số nhóm còn lại sau \(T\) phút.

Ví dụ

5 3
0 1
1 2
2 3
3 2
6 1

3

Nguồn

USACO 2014 December Contest, Silver — Cow Jog. Tác giả đề: Mark Gordon, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=493