$N$ bò của Farmer John ($1 \leq N \leq 100,000$) lại rèn móng, chạy trên đường vô hạn. Vị trí ban đầu khác nhau và một số tốc độ khác nhau.

Đường chia thành làn để vượt nhau. Hai bò cùng làn không bao giờ được cùng vị trí. Không muốn đổi làn hay tốc độ, ông hỏi cần bao nhiêu làn khi chạy $T$ phút ($1 \leq T \leq 1,000,000,000$).

Dữ liệu vào

Dòng đầu chứa $N$, $T$.

$N$ dòng tiếp chứa vị trí ban đầu và tốc độ một bò. Vị trí nguyên không âm, tốc độ nguyên dương; cả hai tối đa một tỷ. Vị trí khác nhau và được cho theo thứ tự tăng.

Dữ liệu ra

In một số nguyên: số làn ít nhất để hai bò cùng làn không bao giờ cùng vị trí, kể cả thời điểm $T$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Tác giả bài toán: Mark Gordon, 2014