IOI '02 - Yong-In, Korea

There is a sequence of $N$ jobs to be processed on one machine. The jobs are numbered from $1$ to $N$, so that the sequence is $1,2,\dots ,N$. The sequence of jobs must be partitioned into one or more batches, where each batch consists of consecutive jobs in the sequence. The processing starts at time $0$. The batches are handled one by one starting from the first batch as follows. If batch $b$ contains jobs with smaller numbers than batch $c$, then batch $b$ is handled before batch $c$. The jobs in a batch are processed successively on the machine. Immediately after all the jobs in a batch are processed, the machine outputs the results of all the jobs in that batch. The output time of a job $j$ is the time when the batch containing $j$ finishes.

A setup time $S$ is needed to setup the machine for each batch. For each job $i$, we know its cost factor $F_i$ and the time $T_i$ required to process it. If a batch contains the jobs $x,x+1,\dots ,x+k$, and starts at time $t$, then the output time of every job in that batch is $t+S+(T_x+T_{x+1}+\cdots +T_{x+k})$. Note that the machine outputs the results of all jobs in a batch at the same time. If the output time of job $i$ is $O_i$, its cost is $O_i\times F_i$. For example, assume that there are $5$ jobs, the setup time $S=1$, $(T_1,T_2,T_3,T_4,T_5)=(1,3,4,2,1)$, and $(F_1,F_2,F_3,F_4,F_5)=(3,2,3,3,4)$. If the jobs are partitioned into three batches $\{1,2\},\{3\},\{4,5\}$, then the output times $(O_1,O_2,O_3,O_4,O_5)=(5,5,10,14,14)$ and the costs of the jobs are $(15,10,30,42,56)$, respectively. The total cost for a partitioning is the sum of the costs of all jobs. The total cost for the example partitioning above is $153$.

You are to write a program which, given the batch setup time and a sequence of jobs with their processing times and cost factors, computes the minimum possible total cost.

Input Specification

The first line contains the number of jobs $N$, $1\le N\le 10000$. The second line contains the batch setup time $S$ which is an integer, $0\le S\le 50$. The following $N$ lines contain information about the jobs $1,2,\dots ,N$ in that order as follows. First on each of these lines is an integer $T_i$, $1\le T_i\le 100$, the processing time of the job. Following that, there is an integer $F_i$, $1\le F_i\le 100$, the cost factor of the job.

Output Specification

The output contains one line, which contains one integer: the minimum possible total cost. This total cost for any partitioning does not exceed $2^{31}-1$.

Sample Input 1

2
50
100 100
100 100

Sample Output 1

45000

Sample Input 2

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

Sample Output 2

153