Điểm chung

Trên trục số Ox, cho \(N\) đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm \(M\) được gọi là nằm trong đoạn thẳng \(AB\) nếu \(A \leq M \leq B\).

Yêu cầu: Đếm xem có bao nhiêu điểm có tọa độ nguyên nằm trong đúng \(K\) đoạn thẳng.

Input

Vào từ file văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên \(N\) và \(K\) (\(1 \leq K \leq N \leq 10^5\));
• \(N\) dòng sau, mỗi dòng gồm hai số nguyên \(a, b\) mô tả hai điểm đầu và cuối của đoạn thẳng (\(1 \leq a \leq b \leq 10^{18}\)).

Output

Ghi ra file văn bản DC.OUT:
Một số nguyên duy nhất là số lượng điểm có tọa độ nguyên nằm trong đúng \(K\) đoạn thẳng.

Example

3 2
1 5
2 8
3 7

3

Scoring

• Có 50% số test ứng với 50% số điểm của bài thỏa mãn: \(a, b \leq 10^3\);
• 30% số test khác ứng với 30% số điểm của bài thỏa mãn: \(K = N\);
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.