弱化版
强化版

之前提到了 $O(n^2)$ 的神奇做法。
现在 $n \leq 3 \times 10^5$，考虑 $O(n)$ 等更优的做法。

$$dp_{i} = \min\limits_{0 \leq j \lt i} \{ dp_{j} + (sc_i - sc_j) \times st_i + (sc_n - sc_j) \times S \}$$

说实话，这个式子长得很板。可以直接想到斜率优化。
然后我推了 5min 就推完了。

设求 $dp_i$ 时，$j_1 \lt j_2 \lt i$，并且 $j_1$ 优于 $j_2$。
则有：

$$dp_{j_1} + (sc_i - sc_{j_1}) \times st_i + (sc_n - sc_{j_1}) \times S \leq dp_{j_2} + (sc_i - sc_{j_2}) \times st_i + (sc_n - sc_{j_2}) \times S$$
$$dp_{j_1} + sc_i \times st_i - sc_{j_1} \times st_i + sc_n \times S - sc_{j_1} \times S \leq dp_{j_2} + sc_i \times st_i - sc_{j_2} \times st_i + sc_n \times S - sc_{j_2} \times S$$
$$dp_{j_1} - sc_{j_1} \times st_i - sc_{j_1} \times S \leq dp_{j_2} - sc_{j_2} \times st_i - sc_{j_2} \times S$$
$$dp_{j_1} - dp_{j_2} - sc_{j_1} \times S + sc_{j_2} \times S \leq sc_{j_1} \times st_i - sc_{j_2} \times st_i$$
移项注意负数变号。
$$\frac{dp_{j_1} - dp_{j_2} - (sc_{j_1} - sc_{j_2}) \times S}{sc_{j_1} - sc_{j_2}} \geq st_i$$
$$\frac{dp_{j_1} - dp_{j_2}}{sc_{j_1} - sc_{j_2}} - S \geq st_i$$

取 $\min$，所以单调队列维护下凸壳。
由于 $st_i$ 单增，可以直接取队头进行转移。

一定不要把 slope(q[l-1],q[l]) 写成 slope(l-1,l)。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 15;
int n, S, c[N], t[N];
int sc[N], st[N];
long long dp[N];
double x(int p) { return sc[p]; }
double y(int p) { return dp[p]; }
double slope(int a, int b) {
    return ((y(a) - y(b)) * 1.0 / (x(a) - x(b))) - S;
}

int q[N], l, r;

int main() {
    scanf("%d%d", &n, &S);
    for (int i = 1; i <= n; i++) scanf("%d%d", &t[i], &c[i]);
    for (int i = 1; i <= n; i++) st[i] = st[i - 1] + t[i], sc[i] = sc[i - 1] + c[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    l = r = 1; q[l] = 0;
    for (int i = 1; i <= n; i++) {
        while (l < r && slope(q[l], q[l + 1]) <= st[i]) l++;  //不满足前一个元素更优
        int j = q[l];
        dp[i] = min(dp[i], dp[j] + (sc[i] - sc[j]) * 1ll * st[i] + (sc[n] - sc[j]) * 1ll * S);
        while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) r--;    //维护下凸壳
        q[++r] = i;
    }
    printf("%lld\n", dp[n]);
    return 0;
}