Batch Scheduling

There is a sequence of $N$ jobs to be processed on one machine. The jobs are numbered from $1$ to $N$, so the sequence is 1, 2, \ldots, 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 a 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 set up 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, \ldots, x+k, and starts at time $t$, 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 $i$ is O_i, its cost is O_i \times F_i.

For example, assume there are $5$ jobs, the setup time is 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 are (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.