P5785 [SDOI2012] Task Scheduling

There are $n$ tasks to be processed on a machine, and they form a sequence. These tasks are numbered from $1$ to $n$, so the order of the sequence is $1, 2, 3 \cdots n$. The $n$ tasks are divided into several batches, and each batch contains several consecutive tasks. Starting from time $0$, the tasks are processed batch by batch. The time required to finish task $i$ alone is $T_i$. Before each batch starts, the machine needs a startup time $s$, and the time needed to finish this batch is the sum of the times of all tasks in the batch. **Note that tasks in the same batch will be completed at the same time.** The cost of each task is its completion time multiplied by a cost coefficient $C_i$. Please determine a batching plan 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 a pair of integers $T_i$ and $C_i$, meaning that the time required to finish task $i$ alone is $T_i$, and its cost coefficient is $C_i$.

One line containing an integer, representing the minimum total cost.

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