Farmer John không giỏi làm nhiều việc cùng lúc. Ông thường xuyên bị xao nhãng, khiến những dự án dài trở nên khó hoàn thành. Hiện tại, ông đang cố sơn một mặt của chuồng bò, nhưng cứ sơn xong một vùng hình chữ nhật nhỏ, ông lại bị phân tâm bởi việc chăm sóc đàn bò, khiến một số phần của chuồng được phủ nhiều lớp sơn hơn những phần khác.

Ta có thể mô tả mặt chuồng bò như một mặt phẳng \(x\)-\(y\) hai chiều. Trên đó, Farmer John sơn \(N\) hình chữ nhật có các cạnh song song với các trục tọa độ; mỗi hình được mô tả bằng tọa độ góc dưới bên trái và góc trên bên phải.

Farmer John muốn phủ vài lớp sơn lên chuồng để không phải sơn lại trong tương lai gần. Tuy nhiên, ông không muốn lãng phí thời gian bằng cách phủ quá nhiều lớp sơn. Hóa ra \(K\) lớp sơn là số lượng tối ưu. Thế nhưng khi nhìn vào diện tích được phủ \(K\) lớp sơn, ông không hài lòng lắm. Ông sẵn sàng sơn thêm không quá hai hình chữ nhật để cố gắng tăng diện tích này, miễn là hai hình chữ nhật ấy không giao nhau (không có chung bất kỳ phần diện tích dương nào). Lưu ý rằng ông cũng có thể quyết định không sơn thêm hình chữ nhật nào hoặc chỉ sơn thêm một hình chữ nhật nếu đó là lựa chọn tốt nhất.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\) (\(1 \leq K, N \leq 10^5\)). Mỗi dòng trong \(N\) dòng còn lại chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một vùng hình chữ nhật được sơn với góc dưới bên trái \((x_1, y_1)\) và góc trên bên phải \((x_2, y_2)\). Tất cả các giá trị \(x\) và \(y\) đều nằm trong phạm vi \(0 \ldots 200\), và mọi hình chữ nhật đều có diện tích dương.

Giống như các hình chữ nhật đã sơn, mọi hình chữ nhật mới mà Farmer John sơn đều phải có diện tích dương, đồng thời các điểm góc của chúng phải có tọa độ \(x\) và \(y\) trong phạm vi \(0 \ldots 200\).

Dữ liệu ra

In ra diện tích lớn nhất của phần chuồng có thể được phủ đúng \(K\) lớp sơn nếu Farmer John sơn thêm không quá hai hình chữ nhật không giao nhau.

Ví dụ

3 2
1 1 4 4
3 3 7 6
2 2 8 7

26

Nguồn

USACO 2019 February Contest, Gold — Painting the Barn

Tác giả: Nick Wu và Brian Dean.