IOI '02 - Yong-In, Korea
There is a sequence of jobs to be processed on one machine. The jobs are numbered from to , so that the sequence is . 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 . The batches are handled one by one starting from the first batch as follows. If batch contains jobs with smaller numbers than batch , then batch is handled before batch . 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 is the time when the batch containing finishes.
A setup time is needed to setup the machine for each batch. For each job , we know its cost factor and the time required to process it. If a batch contains the jobs , and starts at time , then the output time of every job in that batch is . Note that the machine outputs the results of all jobs in a batch at the same time. If the output time of job is , its cost is . For example, assume that there are jobs, the setup time , , and . If the jobs are partitioned into three batches , then the output times and the costs of the jobs are , 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 .
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.
The first line contains the number of jobs , . The second line contains the batch setup time which is an integer, . The following lines contain information about the jobs in that order as follows. First on each of these lines is an integer , , the processing time of the job. Following that, there is an integer , , the cost factor of the job.
The output contains one line, which contains one integer: the minimum possible total cost. This total cost for any partitioning does not exceed .
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2