33OJ
登录 注册

#P17741. [ICPC 2019 Xuzhou R] K-rectangle

[ICPC 2019 Xuzhou R] K-rectangle

Problem Description

There are nn points on the plane, (x1,y1),(x2,y2)…(xn,yn)(x_1, y_1), (x_2, y_2) \dots (x_n, y_n), with xi<xi+1x_i < x_{i+1} and yi>0y_i > 0.

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)

  1. The bottom side of the rectangle should be x-axis
  2. The cost of a rectangle is height×(width+k)\text{height} \times (\text{width} + k) (kk is given by input)
  3. Any two different rectangles can't have an intersection
  4. The rectangle can degenerate to two lines, which means width=0\text{width} = 0

Please calculate the minimum cost to cover all of the points.

Input Format

The first line contains two integers, nn and kk (1≤n≤4×105,1≤k≤1061 \le n \le 4\times10^5, 1\le k \le 10^6) --- the number of points and the coefficient described in the problem.

Each of the next nn lines contains two integers, xix_i and yiy_i (−106≤xi≤106,1≤yi≤106-10^6 \le x_i \le 10^6, 1\le y_i \le 10^6) --- meaning the ithi^{th} point is at (xi,yi)(x_i, y_i).

Output Format

Output the minimum cost to cover all of the points.

1 2
-666 666
1332
2 66666
-666 666
666 666
45286668