Description

Original source: JoyOI TYVJ 1098

There are $N$ tasks arranged in a sequence waiting to be executed on a machine, and their order cannot be changed. The machine will divide these $N$ tasks into several batches, each containing a consecutive set of tasks. Starting from time $0$, the tasks are processed in batches. The time required to execute the $i$-th task is $T_i$. Additionally, before each batch of tasks starts, the machine requires a startup time of $S$, so the total time to execute a batch of tasks is the startup time $S$ plus the sum of the time required for each task in the batch.

After a task is executed, it waits briefly in the machine until all tasks in the batch are completed. That is, all tasks in the same batch will finish at the same time. The cost of each task is its completion time multiplied by a cost coefficient $C_i$.

Please plan a grouping scheme for the machine to minimize the total cost.

Input Format

The first line contains $N$. The second line contains $S$.

The next $N$ lines each contain a pair of positive integers, $T_i$ and $C_i$, indicating that the $i$-th task requires $T_i$ time to complete and has a cost coefficient $C_i$.

Output Format

A single number, the minimum total cost.

Sample 1

The grouping scheme is $\{1,2\},\{3\},\{4,5\}$. The completion times are $\{5,5,10,14,14\}$, and the costs $C=\{15,10,30,42,56\}$, resulting in a total cost of $153$.

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

153

Data Range and Hints

For all data, $1\le N\le 5000,0\le S\le 50,1\le T_i,C_i\le 100$.