Để thực hiện chương trình "Bảo vệ môi trường xanh sạch đẹp", tỉnh Đoàn Bình Định đã phát động phong trào trồng cây xanh trên vùng đất trống dành cho đối tượng học sinh. Vùng đất trồng có hình dạng một hình chữ nhật kích thước 10^9 × 10^9 . Khi mới trồng các cây con, học sinh cần che chắn để tránh nắng chiều lên phần diện tích để trồng trọt. Có tất cả n tấm chắn để có thể che chắn vùng đất. Mỗi tấm chắn đều có hình chữ nhật cạnh song song với cạnh của vùng đất, góc dưới trái của tấm chắn đặt ở tọa độ (0, 0), tấm chắn thứ i có tọa độ đỉnh trên phải là (xi , yi). Do hạn chế về mặt kinh phí, tỉnh Đoàn chỉ cho phép học sinh được chọn k tấm chắn để che chắn cho vùng đất.

Yêu cầu: Hãy xác định diện tích lớn nhất có thể được đồng thời bảo vệ bởi k tấm chắn.

Dữ liệu: Vào từ file văn bản TREE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 2 × 10^5 ).
• Dòng thứ i trong n dòng sau chứa hai số nguyên xi , y i (1 ≤ xi , y i ≤ 10^9 )

Kết quả: Đưa ra file văn bản TREE.OUT một số nguyên duy nhất là diện tích lớn nhất được đồng thời bảo vệ bởi k tấm chắn.

Ví dụ:

Input

5 3
3 5
2 2
2 5
4 4
5 3

Output

9

Ràng buộc:

• Subtask 1 (50% số điểm): 1 ≤ k ≤ n ≤ 3 × 10^3

• Subtask 2 (50% số điểm): 1 ≤ k ≤ n ≤ 2 × 10^5

  Bản PDF