Background

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.

Problem Description

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.

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

Output Format

One line with one integer, representing 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$, $0 \le C_i \le 2^8$.

Translated by ChatGPT 5