## IOI '02 P4 - Batch Scheduling

View as PDF

Points: 20 (partial)
Time limit: 0.02s
Java 0.08s
Memory limit: 32M

Problem type
##### 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.

#### Input Specification

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.

#### 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 .

#### 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