好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

有 $N$ 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。从时刻 $0$ 开始，任务被分批加工，执行第 $i$ 个任务所需的时间是 $T_i$。另外，在每批任务开始前，机器需要 $S$ 的启动时间，故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。

请为机器规划一个分组方案，使得总费用最小。

---

输入格式

第一行一个整数 $N$；

第二行一个整数 $S$；

接下来 $N$ 行，每行两个正整数 $T_i, C_i$，表示第 $i$ 个任务单独完成所需的时间是 $T_i$ 及其费用系数 $C_i$。

---

输出格式

输出一个整数，表示最小的总费用。

---

样例

样例输入

5
1
1 3
3 2
4 3
2 3
1 4

样例输出

153

样例说明

与上一题（任务安排 1）样例相同，数据规模扩大。

$N=5, S=1$，任务数据：

• 任务1: T=1, C=3
• 任务2: T=3, C=2
• 任务3: T=4, C=3
• 任务4: T=2, C=3
• 任务5: T=1, C=4

最优分组方案为 $\{1,2\}, \{3\}, \{4,5\}$，总费用 $153$（计算过程同上一题）。

---

数据范围

对于全部数据：

• $1 \le N \le 10^4$
• $0 \le S \le 50$
• $1 \le T_i, C_i \le 100$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 任务安排 问题的优化版本，数据范围增大到 $N \le 10^4$，需要 $O(N \log N)$ 或 $O(N)$ 解法。

在上一题（任务安排 1）中，转移方程为：

$$dp[i] = \min_{0 \le j < i} \left\{ dp[j] + \text{sumT}[i] \times (\text{sumC}[i] - \text{sumC}[j]) + S \times (\text{sumC}[N] - \text{sumC}[j]) \right\}$$

其中 $\text{sumT}[i] = \sum_{k=1}^i T_k$，$\text{sumC}[i] = \sum_{k=1}^i C_k$。

展开：

$$dp[i] = \min_{0 \le j < i} \left\{ dp[j] - (\text{sumT}[i] + S) \times \text{sumC}[j] \right\} + \text{sumT}[i] \times \text{sumC}[i] + S \times \text{sumC}[N]$$

令 $A[i] = \text{sumC}[i]$，$B[i] = dp[i] - (\text{sumT}[i] + S) \times \text{sumC}[i]$，则转移变为：

$$dp[i] = \min_{0 \le j < i} \left\{ B[j] + (\text{sumT}[i] + S) \times A[j] \right\} + \text{sumT}[i] \times \text{sumC}[i] + S \times \text{sumC}[N]$$

这是形如 $dp[i] = \min\{ b[j] + k \cdot a[j] \}$ 的形式，可以用 斜率优化（凸包优化）将复杂度从 $O(N^2)$ 降为 $O(N)$。

斜率优化： 设对于 $j_1 < j_2$，决策 $j_2$ 优于 $j_1$ 的条件为：

$$\frac{B[j_2] - B[j_1]}{A[j_2] - A[j_1]} \le \text{sumT}[i] + S$$

由于 $\text{sumT}[i] + S$ 单调递增（$T_i > 0$），$A[i] = \text{sumC}[i]$ 单调递增（$C_i > 0$），因此可以用单调队列维护下凸包。

步骤：

1. 计算前缀和 $\text{sumT}[i]$, $\text{sumC}[i]$；
2. 初始化队列，将 $j=0$ 入队（对应 $A[0]=0, B[0]=0$）；
3. 遍历 $i$ 从 $1$ 到 $N$：
   • 若队首两点斜率 $\le \text{sumT}[i] + S$，则队首决策优于队首下一个，弹出队首；
   • 取队首作为最优决策 $j$，计算 $dp[i]$；
   • 将 $(A[i], B[i])$ 加入队尾，维护凸包性质：若队尾两点与 $i$ 形成上凸，则弹出队尾；
4. 输出 $dp[N]$。

复杂度 $O(N)$。

注意：本题 $T_i, C_i$ 为正，前缀和单调递增，斜率优化条件满足。如果 $T_i$ 可能为负数（本题没有），则需要二分查找最优决策点。