Batch Task Scheduling for Minimum Total Cost

You are given a sequence of n tasks numbered from 1 to n. Each task i has a processing time \(T_i\) and a cost coefficient \(C_i\). The tasks must be processed in the given order, but you may partition them into one or more contiguous batches.

Processing is done batch‐by‐batch starting from time 0. Before processing each batch, the machine requires a startup time \(s\). Suppose a batch consists of tasks \(i+1,i+2,\dots,j\). All tasks in the batch finish at the same time, which is computed as follows. Let the finishing time after processing the first \(i\) tasks be \(F(i)\). Then the finishing time for tasks \(i+1\) through \(j\) is \[ F(j)=F(i)+s+\sum_{k=i+1}^{j}T_k. \] In particular, if no previous task exists (i.e. \(i=0\) and we define \(F(0)=0\)) then the finishing time of the first batch is \[ F(j)=s+\sum_{k=1}^{j}T_k. \]

The cost incurred for task \(k\) is defined as its finishing time multiplied by its cost coefficient, i.e. \[ \text{cost}_k = F(j) \times C_k \quad \text{for } k \text{ in the batch finishing at } F(j). \] Your goal is to choose a partition of the tasks into batches so that the total cost: \[ \sum_{\text{batches}}\; F(\text{batch end}) \times \Bigl(\text{sum of } C_i \text{ in the batch}\Bigr) \] is minimized.

Input Format
The first line contains two integers \(n\) and \(s\) -- the number of tasks and the machine startup time respectively. Each of the next \(n\) lines contains two integers \(T_i\) and \(C_i\) representing the processing time and cost coefficient of the \(i\)th task.

Output Format
Output a single integer representing the minimum total cost.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two space-separated integers \(n\) and \(s\). Following this, there are \(n\) lines; the \(i\)th line contains two space-separated integers \(T_i\) and \(C_i\).

Example:
3 1 1 1 2 3 3 2

outputFormat

Output a single integer: the minimum total cost to complete all tasks.

Example: for the above input, the correct output is 32.

sample

3 1
1 1
2 3
3 2

32