Đoạn phủ mạnh

Trên trục số, bạn được cho \(N\) đoạn thẳng \([L_1; R_1], [L_2; R_2], \ldots, [L_N; R_N]\) với tọa độ đầu mút là các số nguyên dương.

Một thao tác chia nhỏ sẽ thay thế đoạn thẳng \([L; R]\) bằng hai đoạn \([L; M]\) và \([M; R]\), trong đó \(M\) là một số nguyên dương và \(L < M < R\). Bạn có thể chia cả những đoạn ban đầu lẫn những đoạn mới sinh ra sau các lần chia trước đó.

Ta nói đoạn thẳng \([A; B]\), trong đó \(A < B\) và \(A, B\) là các số nguyên dương, phù mạnh đoạn \([L; R]\) nếu đoạn \([A; B]\) bao phủ ít nhất một nửa độ dài của đoạn \([L; R]\).

Yêu cầu: Tìm độ dài ngắn nhất có thể của một đoạn thẳng \([A; B]\) sao cho sau khi thực hiện chính xác \(K\) thao tác chia nhỏ, đoạn \([A; B]\) phủ mạnh tất cả \(N + K\) đoạn thẳng cuối cùng.

Input

Vào từ tệp văn bản SEGCOV.INP:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) \((1 \le N \le 10^5,\ 0 \le K \le 10^{14})\);
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\) \((1 \le L_i < R_i \le 10^9)\), biểu diễn đoạn thẳng thứ \(i\).

Biết rằng, luôn tồn tại \(K\) thao tác chia nhỏ từ các đoạn đã cho và một số đoạn đầu vào có thể trùng nhau hoàn toàn.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra tệp văn bản SEGCOV.OUT một số nguyên duy nhất là độ dài nhỏ nhất có thể của đoạn thẳng \([A; B]\) sao cho \([A; B]\) phù mạnh tất cả các đoạn cuối cùng nhận được sau \(K\) thao tác chia nhỏ.

Example

3 3
1 7
3 8
2 9

4

6 15
4 10
2 8
7 14
1 9
5 12
3 13

7

Scoring

• Subtask 1 (15% số điểm): \(K = 0\);
• Subtask 2 (15% số điểm): không có hai đoạn thẳng nào giao nhau;
• Subtask 3 (10% số điểm): \(N \le 500\), \(R_i \le 500\);
• Subtask 4 (20% số điểm): \(N \le 5000\), \(R_i \le 5000\);
• Subtask 5 (20% số điểm): \(N \le 10^4\);
• Subtask 6 (20% số điểm): không có ràng buộc gì thêm.