P17741 [ICPC 2019 Xuzhou R] K-rectangle

平面上有 $n$ 个点，坐标分别为 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，满足 $x_i < x_{i+1}$ 且 $y_i > 0$。 你需要放置若干个矩形来覆盖所有这些点，并遵循以下约束条件。（若一个点位于矩形内部或矩形边上，则称该点被覆盖） 1. 矩形的底边必须落在 **$x$ 轴**上。 2. 一个矩形的代价为 $\text{高度} \times (\text{宽度} + k)$，其中 $k$ 由输入给定。 3. 任意两个不同的矩形不能有交集。 4. 矩形可以退化为两条线，即 $\text{宽度} = 0$。 请计算覆盖所有点的最小总代价。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 4\times10^5$，$1\le k \le 10^6$）—— 点的个数与题目中描述的系数。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^6 \le x_i \le 10^6$，$1\le y_i \le 10^6$）—— 表示第 $i$ 个点位于 $(x_i, y_i)$。

输出覆盖所有点的最小总代价。

翻译由 DeepSeek V4 Pro 完成