Thiết bị thông minh

Công ty S-HOME đang thiết kế một mẫu nhà thông minh thế hệ mới được trang bị $K$ thiết bị thông minh. Bản thiết kế được vẽ trên mặt phẳng toạ độ $Oxy$ với gốc toạ độ $(0,0)$ là nơi đặt trung tâm điều khiển tất cả các thiết bị. Trên bản vẽ, kỹ sư thiết kế vạch ra $N$ vùng hình chữ nhật quan trọng có các cạnh song song với hai trục $Ox$ và $Oy$, nơi mà các thiết bị thông minh có thể được đặt vào. Các vùng hình chữ nhật được đánh số từ $1$ đến $N$, vùng thứ $i$ $(1\le i\le N)$ được cho bởi bộ $(L_i,B_i,R_i,T_i)$ với toạ độ góc trái dưới là $(L_i,B_i)$ và góc phải trên là $(R_i,T_i)$. Lưu ý rằng các vùng hình chữ nhật này có thể giao nhau.

Mỗi thiết bị thông minh sẽ được đặt tại một điểm có toạ độ nguyên dương $(x,y)$ và phải nằm trong hoặc nằm trên cạnh của ít nhất một vùng hình chữ nhật quan trọng. Thiết bị này được điều khiển trực tiếp bởi trung tâm điều khiển tại $(0,0)$ và có chi phí lắp đặt kết nối bằng $(x+y)$. Điểm $(x,y)$ gọi là nằm trong hoặc trên cạnh vùng hình chữ nhật quan trọng thứ $i$ khi và chỉ khi $L_i\le x\le R_i$ và $B_i\le y\le T_i$.

Yêu cầu: Hãy giúp công ty S-HOME xác định $K$ vị trí đặt thiết bị thông minh để chi phí lớn nhất trong số các chi phí lắp đặt kết nối tới trung tâm điều khiển của $K$ thiết bị nêu trên là nhỏ nhất. Lưu ý rằng các thiết bị thông minh không được đặt trùng vị trí của nhau.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $N$ và $K$ $(N\le 50000;K\le {10}^{18})$.
• Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa bốn số nguyên dương $L_i$, $B_i$, $R_i$, $T_i$ $(L_i<R_i\le 5\times {10}^7;B_i<T_i\le 5\times {10}^7)$.

Dữ liệu đảm bảo giá trị $K$ không lớn hơn tổng số điểm có toạ độ nguyên dương nằm trong hoặc trên cạnh của ít nhất một vùng hình chữ nhật quan trọng.

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

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị nhỏ nhất tìm được của chi phí lớn nhất trong số các chi phí lắp đặt kết nối tới trung tâm điều khiển của $K$ thiết bị.

Ràng buộc

• $1\le N\le 50000$; $1\le K\le {10}^{18}$.
• $1\le L_i<R_i\le 5\times {10}^7$; $1\le B_i<T_i\le 5\times {10}^7$.
• $K$ không lớn hơn tổng số điểm có toạ độ nguyên dương nằm trong hoặc trên cạnh của ít nhất một vùng hình chữ nhật quan trọng.

Subtasks

• Subtask 1 ($16\%$ số điểm): $N\le 100$; $R_i,T_i\le 1000$ với mọi $i=1,2,\dots ,N$.
• Subtask 2 ($20\%$ số điểm): $N\le 15$.
• Subtask 3 ($16\%$ số điểm): $N\le 1000$.
• Subtask 4 ($20\%$ số điểm): $R_i,T_i\le {10}^5$ với mọi $i=1,2,\dots ,N$.
• Subtask 5 ($16\%$ số điểm): $K\le {10}^5$.
• Subtask 6 ($12\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ