Background

This problem is an enhanced version of P5785 and P10980.

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

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 complete 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

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