好久没写题解了，写一篇找找感觉吧（
首先发现答案不超过 \(3k\)，也就是说，我们选择的三角形的高度是 \(\mathcal O(\sqrt{k})\) 级别的，准确来说，\(\sqrt{6k}\)。故对于 \(y>\sqrt{6k}\) 的点我们肯定会选择花费 \(3\) 的代价使用 1 操作将其搞定。
接下来考虑怎样处理 \(y\le\sqrt{6k}\) 的部分的贡献。考虑从右到左处理，设 \(dp_{i,j}\) 表示目前钦定了 \(i\) 之后的部分的高度，第 \(i\) 列的高度为 \(j\) 的最小代价，那么有转移 \(dp_{i,j}+w(i-1,j)\to dp_{i-1,j+1},dp_{i,j}+w(i-1,k)+\dfrac{k(k+1)}{2}\to dp_{i-1,k}\)，其中 \(w(i,j)=3\sum\limits_{x_k=i,y_k>j}1\)
时间复杂度 \(n\sqrt{k}\)。
const int MAXN = 1e5;
const int INF = 0x3f3f3f3f;
int n, k, dp[MAXN + 5];
vector<int> vec[MAXN + 5];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1, x, y; i <= k; i++) scanf("%d%d", &x, &y), vec[y].pb(n - x + 1);
for (int i = n; i; i--) {
int lim = min(800, n - i + 1);
for (int pos : vec[i]) {
for (int j = 0; j <= min(lim, pos - 1); j++) {
chkmin(dp[pos], dp[j]); dp[j] += 3;
}
}
static int tmp[MAXN + 5]; tmp[0] = dp[0];
for (int j = 0; j <= lim; j++) {
tmp[j + 1] = dp[j];
chkmin(tmp[0], dp[j] + j * (j + 1) / 2 + 2);
}
for (int j = 0; j <= lim + 1; j++) dp[j] = tmp[j];
}
printf("%d\n", dp[0]);
return 0;
}