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

Đường đua được chia thành nhiều làn để các con bò có thể vượt qua nhau. Hai con bò trong cùng một làn không bao giờ được chiếm cùng một vị trí. Farmer John không muốn bất kỳ con bò nào phải đổi làn hay điều chỉnh tốc độ, và ông muốn biết cần bao nhiêu làn để đáp ứng điều này nếu đàn bò sẽ chạy trong \(T\) phút (\(1 \le T \le 1\,000\,000\,000\)).

Dữ liệu vào

Dòng đầu tiên chứa \(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 con bò. Vị trí là một số nguyên không âm và 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 con 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 một số nguyên duy nhất cho biết số làn tối thiểu cần thiết để không có hai con bò nào trong cùng một làn từng chiếm cùng một vị trí (kể cả tại thời điểm \(T\)).

Ví dụ

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

3

Nguồn

USACO 2014 December Contest, Gold - Cow Jog: https://usaco.org/index.php?page=viewproblem2&cpid=496

Tác giả: Mark Gordon, 2014.