P10979 Task Scheduling 2

This problem is an enhanced version of P2365 and a simplified version of P5785. It is used to help students gradually understand slope-optimized DP.

There are $n$ tasks to be processed on a machine, forming a sequence. The tasks are numbered from $1$ to $n$, so the order is $1, 2, 3 \cdots n$. These $n$ tasks are divided into several batches, and each batch contains several adjacent tasks. Starting from time $0$, the tasks are processed batch by batch. The time needed to finish task $i$ alone is $T_i$. Before starting each batch, the machine needs a startup time $s$, and the time to finish this batch is the sum of the times of all tasks in it. **Note that tasks in the same batch will be completed at the same time**. The cost of each task equals its completion time multiplied by a cost coefficient $C_i$. Please determine a batching scheme that minimizes the total cost.

The first line contains an integer $n$. The second line contains an integer $s$. The next $n$ lines each contain two integers $T_i$ and $C_i$, meaning that the time needed to finish task $i$ alone is $T_i$, and its cost coefficient is $C_i$.

One line with one integer, representing the minimum total cost.

For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$, $1 \le s \le 2^8$, $1 \le T_i \le 2^8$, $0 \le C_i \le 2^8$. Translated by ChatGPT 5