#include using namespace std; typedef long long LL; const int N = 300010; int n, s; LL t[N], c[N], f[N]; int q[N]; int main() { cin >> n >> s; for (int i = 1; i <= n; i++) cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1]; // 初始化队列 int hh = 0, tt = 0; // 添加哨兵 for (int i = 1; i <= n; i++) { // 动态规划,从小到大枚举每个i int l = hh, r = tt; // 通过二分upper_bound,找到第一个斜率大于k=st[i] + S的两个点,起点就是切点 while (l < r) { int mid = (l + r) / 2; // check函数 if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) r = mid; else l = mid + 1; } int j = q[l]; // 切点位置 // 动态规划 f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]; // 出队尾,斜率比自己大的点都要出凸包队列,小心long long的乘法 while (hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt--; q[++tt] = i; } cout << f[n] << endl; return 0; }