Batch Scheduling

A single machine processes $N$ jobs numbered $1$ through $N$ in order. The job sequence $1, 2, \dots, N$ must be split into one or more batches, where each batch is a group of consecutive jobs.

Processing starts at time $0$. The batches are handled one at a time starting from the first, and a batch containing lower-numbered jobs is handled before one containing higher-numbered jobs. Before each batch, the machine needs a setup time $S$.

If a batch consists of jobs $x, x+1, \dots, x+k$ and starts at time $t$, then the output (completion) time of every job in that batch is $t + S + (T_x + T_{x+1} + \dots + T_{x+k}).$ The machine outputs all results of a batch at the same time, and the next batch starts immediately afterward.

Each job $i$ has a processing time $T_i$ and a cost factor $F_i$. If the output time of job $i$ is $O_i$, its cost is $O_i \times F_i$. The total cost of a partition is the sum of the costs of all jobs.

Given the setup time together with each job's processing time and cost factor, write a program that computes the minimum possible total cost.

The first line contains the number of jobs $N$ ($1 \le N \le 10000$).

The second line contains the setup time $S$ as an integer ($0 \le S \le 50$).

Each of the next $N$ lines describes jobs $1, 2, \dots, N$ in order. Each line contains two integers $T_i$ and $F_i$, where $T_i$ is the processing time of the job ($1 \le T_i \le 100$) and $F_i$ is its cost factor ($1 \le F_i \le 100$).

Print the minimum possible total cost as a single integer on one line.

For every test case, the total cost of any partition does not exceed $2^{31} - 1$.