Trong tín ngưỡng Baltic cổ, việc giữ cho ngọn lửa thiêng luôn cháy có ý nghĩa quan trọng. Một vị tư tế được gọi là krivis có trách nhiệm bảo vệ ngọn lửa, không để nó tắt. Ông có nhiều nữ trợ tá đáng tin cậy, được gọi là vaidilutės, và muốn lập lịch để họ tiếp lửa và trông coi ngọn lửa. Ông phải bảo đảm luôn có một vaidilutė chăm sóc ngọn lửa.

Krivis sử dụng hệ thống đo thời gian riêng, trong đó mỗi ngày có \(M\) phút. Trong làng có \(N\) vaidilutės. Khoảng thời gian mà vaidilutė thứ \(i\) có thể làm việc được mô tả bởi hai số nguyên \(s_i\) và \(e_i\). Số \(s_i\) là thời điểm sớm nhất trong ngày mà cô có thể bắt đầu làm việc, còn \(e_i\) là thời điểm muộn nhất trong ngày mà cô phải kết thúc công việc. Thời gian được tính bằng số phút kể từ đầu ngày. Lưu ý rằng nếu \(s_i>e_i\), cô sẵn sàng làm việc qua đêm.

Krivis nhờ bạn chọn một số vaidilutės và sắp xếp ca làm việc cho họ. Mỗi vaidilutė được chọn phải bắt đầu ca không sớm hơn \(s_i\) và kết thúc ca không muộn hơn \(e_i\). Một ca làm việc luôn ngắn hơn một ngày trọn vẹn. Những vaidilutės được chọn sẽ lặp lại ca làm việc của mình hằng ngày.

Việc bàn giao công việc giữa hai vaidilutės làm tăng nguy cơ ngọn lửa bị tắt. Vì vậy, bạn muốn giảm thiểu số lần bàn giao trong ngày bằng cách lập lịch cần ít vaidilutės nhất có thể.

Hãy tính số vaidilutės ít nhất cần chọn để ngọn lửa thiêng được chăm sóc tại mọi thời điểm.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số vaidilutės có thể làm việc và số phút trong một ngày.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(s_i\) và \(e_i\), lần lượt là thời điểm bắt đầu sớm nhất và thời điểm kết thúc muộn nhất của vaidilutė thứ \(i\).

Dữ liệu ra

In ra một số nguyên là số vaidilutės ít nhất cần chọn. Nếu không thể chọn các vaidilutės để đáp ứng yêu cầu, in ra \(-1\).

Ràng buộc

• \(1\le N\le 2\cdot 10^5\).
• \(2\le M\le 10^9\).
• \(0\le s_i,e_i<M\) với mọi \(1\le i\le N\).
• \(s_i\ne e_i\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(14\) điểm: \(N\le 20\).
2. \(17\) điểm: \(N\le 300\).
3. \(9\) điểm: \(N\le 5000\).
4. \(13\) điểm: với mọi \(1\le i\le N\), \(s_i<e_i\) hoặc \(e_i=0\).
5. \(21\) điểm: khoảng thời gian từ \(s_i\) đến \(e_i\) có cùng độ dài đối với mọi vaidilutė, tính cả trường hợp khoảng thời gian đi qua nửa đêm.
6. \(26\) điểm: không có ràng buộc bổ sung.

Ví dụ

4 100
10 30
30 70
20 40
60 20

3

1 100
30 40

-1