Background

This problem is an enhanced version of P10979, designed to help students gradually understand slope optimization DP.

Problem Description

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: 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.

Input Format

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 required to complete task $i$ alone is $T_i$, and its cost coefficient is $C_i$.

Output Format

One line containing one integer, the minimum total cost.

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

153

Hint

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$, $|C_i| \le 2^8$.

Translated by ChatGPT 5