P10981 Task Scheduling 4.2【No Data】

This problem is an enhanced version of P5785 and P10980.

There are $n$ tasks to be processed on a machine, forming 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 adjacent tasks. Starting from time $0$, the tasks are processed batch by batch. The time required to complete task $i$ alone is $T_i$. Before each batch starts, the machine needs a startup time $s$, and the time required to finish this batch is the sum of the times required by 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$. 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 complete task $i$ alone is $T_i$, and its cost coefficient is $C_i$.

One line containing an 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$, $|T_i| \le 2^8$, $|C_i| \le 2^8$. Translated by ChatGPT 5