Minimum Disjoint Rectangles Covering Points

Given n points in the plane (each with integer coordinates) and an integer k, the task is to cover all the points with exactly k axis‐parallel rectangles such that the sum of their areas is minimized. A rectangle that covers only one point has an area of 0; similarly, a rectangle covering points that lie on a single horizontal or vertical line has an area of 0. In addition, the k rectangles must be completely separated; that is, no two rectangles are allowed to share any boundary (edges or vertices).

Note (in LaTeX): For a set of points covered by a rectangle, if the minimum and maximum x‐coordinates are \(x_{min}\) and \(x_{max}\) and the minimum and maximum y‐coordinates are \(y_{min}\) and \(y_{max}\), then the area is defined as:

[ \text{Area} = (x_{max} - x_{min}) \times (y_{max} - y_{min}). ]

When two points have the same x or y coordinate, the rectangle covering them can be chosen to be degenerate (with zero width or height) hence its area is 0. However, if points in different groups are separated by a common coordinate value (for example, two adjacent groups with the same x value), then the corresponding rectangles would share a boundary which is not allowed. In an optimal solution the sets of points covered by each rectangle must be separable by a gap: there must exist an index in one ordering (either by x‐coordinate or by y‐coordinate) such that the maximum coordinate in one group is strictly less than the minimum coordinate in the next group.

Your task is to compute the minimum total area of k disjoint rectangles that cover all the given points. It is guaranteed that an answer exists.

inputFormat

The first line contains two integers n and k (number of points and number of rectangles). The next n lines each contain two integers x and y, representing the coordinates of a point.

Example:

4 2
1 1
2 2
3 6
0 7

outputFormat

Output a single integer representing the minimum total area of the k disjoint rectangles covering all points.

Example:

4

sample

4 2
1 1
2 2
3 6
0 7

4