Problem Description

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.

Input Format

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

Output Format

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

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

153

Hint

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