首先，不存在 \(H_i < H_j\) 时增高 \(H_i\) 至 \(H_j + 1\) 后连 \(i \to j\) 更优，因为增高后原来能连 \(i\) 的点现在不一定能连 \(i\) 了，原来能连 \(j\) 的点还是能连 \(j\)，此时的方案集必然是原方案集的子集，答案一定不会更优，又因为你付出了增高的费用，所以这样一定劣。
那么我们就只会对存在 \(j \ne i\)，满足 \(H_j = H_i, C_j \le C_i\) 的点 \(i\) 增高。
所以可以把高度离散化到 \(O(n)\) 个，留 \(H_i, H_i + 1\) 即可。
考虑 DP。
增高是不好判断的，考虑通过状态上的限制来完成增高。
我们以高度为横轴，相同高度按 \(C_i\) 填点。
样例就可以画成这样：
最后出答案的图长这样：
记图上第 \(i\) 个高度下的最大纵坐标为 \(y_i\)，则对于任一高度 \(j\)，其所能容纳的最多无需付费的点的数量就是 \(\max\limits_{k=0}^{j-1} y_k\)，记这个数量为 \(t_j\)，显然 \(t_j\) 不降。
我们考虑限制 \(t_j\) 来使得一些点被迫增高。
设 \(f(i, j, k)\) 表示填完前 \(i - 1\) 个高度，现在在填第 \(i\) 个高度，此前所有高度的 \(y\) 的最大值为 \(j\)，前 \(i - 1\) 个高度给当前高度剩了 \(k\) 个点的最小花费。
初值：\(f(i, j, k) = +\infin, f(0, 1, 0) = 0\)；答案：\(\min\limits_{j=1}^n f(m, j, 0)\)，其中 \(m\) 为离散化后的高度数。
我们可以通过付出 \(mn\) 的代价来增加一个连接装置，使 \(t_i\) 增加 \(1\)，至于哪个点增加，贪心选最小的即可。记 \(mn\) 为高度小于第 \(i\) 个高度的点中 \(C_i\) 的最小值，则有：
\[f(i, j, k) + mn \to f(i, j + 1, k) \]然后就是填点：
\[f(i, j, k) + F(j, h_{i+1} - h_i, k + cnt_i) \times K \to f(i + 1, j, \max\{k + cnt_i - (h_{i+1} - h_i)j, 0\}) \]其中 \(F(n, m, k)\) 表示将 \(k\) 个点放到最大点数为 \(m\) 的个 \(n\) 个高度中的增高操作次数，显然可以 \(\mathcal O(1)\) 计算。
\(f(i, j, k)\) 可以滚动掉 \(i\) 一维，但没必要。
时间复杂度 \(\mathcal O(n^3)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 310;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
int n, h[N], c[N], cnt[N << 1], mnc[N << 1];
ll K, f[N << 1][N][N];
vector<int> hs;
inline ll F(int n, int m, int k) {
n = min(n, k / m);
return n * (n - 1) / 2 * m + n * (k - n * m);
}
inline void chkmin(int &lhs, int rhs) {lhs = min(lhs, rhs);}
inline void chkmin(ll &lhs, ll rhs) {lhs = min(lhs, rhs);}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> K;
for (int i = 1; i <= n; i++) cin >> h[i] >> c[i], hs.emplace_back(h[i]), hs.emplace_back(h[i] + 1);
sort(hs.begin(), hs.end()); hs.erase(unique(hs.begin(), hs.end()), hs.end());
memset(mnc, 0x3f, sizeof(mnc));
for (int i = 1; i <= n; i++) {
h[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin();
cnt[h[i]]++, chkmin(mnc[h[i]], c[i]);
}
memset(f, 0x3f, sizeof(f)), f[0][1][0] = 0;
int m = hs.size(), mn = 2e9;
for (int i = 0; i < m; i++) {
int wid = i + 1 < m ? min(n, hs[i + 1] - hs[i]) : n;
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= n; k++) if (f[i][j][k] < INF) {
chkmin(f[i][j + 1][k], f[i][j][k] + mn);
chkmin(f[i + 1][j][max(k + cnt[i] - wid * j, 0)], f[i][j][k] + F(wid, j, k + cnt[i]) * K);
}
}
mn = min(mn, mnc[i]);
}
ll ans = INF;
for (int j = 1; j <= n; j++) ans = min(ans, f[m][j][0]);
cout << ans;
return 0;
}