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. Hãy giúp ông xác định diện tích chuồng được phủ đúng \(K\) lớp sơn sau khi ông sơn tất cả các hình chữ nhật của mình.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\) (\(1 \leq K \leq 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 1000\), và mọi hình chữ nhật đều có diện tích dương.

Dữ liệu ra

In ra diện tích của phần chuồng được phủ đúng \(K\) lớp sơn.

Ví dụ

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

8

Nguồn

USACO 2019 February Contest, Silver — Painting the Barn

Tác giả: Nick Wu.