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} + \dots + 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 10\,000~. 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