Description

There are $n$ tasks arranged in a sequence waiting to be completed on a single machine (the order cannot be changed). These $n$ tasks are divided into several batches, each batch containing consecutive 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 process that batch is the sum of the required times of its tasks (all tasks in the same batch finish at the same time).

The cost of each task is its completion time multiplied by a cost coefficient $f_i$. Determine a batching scheme that minimizes the total cost.

Input Format

The first line contains a positive integer $n$.
The second line contains an integer $s$.
Each of the next $n$ lines contains a pair of numbers, $t_i$ and $f_i$, indicating that the time required to complete task $i$ alone is $t_i$ and its cost coefficient is $f_i$.

Output Format

Output a single number, the minimal 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 5000$, $0 \le s \le 50$, $1 \le t_i, f_i \le 100$.

Sample explanation
If the batching scheme is $\{1,2\}, \{3\}, \{4,5\}$, then the completion times are $\{5, 5, 10, 14, 14\}$, the cost is $C=15+10+30+42+56$, so the total cost is $153$.

Translated by ChatGPT 5