#P17741. [ICPC 2019 Xuzhou R] K-rectangle
[ICPC 2019 Xuzhou R] K-rectangle
Problem Description
There are points on the plane, , with and .
You need to place several rectangles to cover all of them with the following constraints. (A point is covered if it lies inside the rectangle or on the side of the rectangle)
- The bottom side of the rectangle should be x-axis
- The cost of a rectangle is ( is given by input)
- Any two different rectangles can't have an intersection
- The rectangle can degenerate to two lines, which means
Please calculate the minimum cost to cover all of the points.
Input Format
The first line contains two integers, and () --- the number of points and the coefficient described in the problem.
Each of the next lines contains two integers, and () --- meaning the point is at .
Output Format
Output the minimum cost to cover all of the points.
1 2
-666 666
1332
2 66666
-666 666
666 666
45286668