Batch Scheduling with Startup Time

You are given n tasks arranged in a fixed order. These tasks need to be processed on a single machine. The tasks are grouped into batches; each batch is a consecutive subsequence of tasks. The processing starts at time 0, and batches are processed one by one.

Before processing any batch, the machine requires a fixed startup time s. In a batch containing tasks i from l to r, the processing time is the sum \(\sum_{i=l}^{r} t_i\). All tasks in the same batch finish simultaneously at the batch finish time. In particular, if the previous batch finished at time \(F_{prev}\), then the finish time of the current batch is

[ F = F_{prev} + s + \sum_{i=l}^{r} t_i. ]

The cost for a task \(i\) is defined as its finish time multiplied by a cost coefficient \(f_i\). That is, if task \(i\) is in a batch that finishes at time \(F\), its cost is \(F \times f_i\). The total cost is the sum of the individual costs for all tasks.

Your goal is to determine how to partition the tasks into batches (preserving the original order) so that the total cost is minimized.

Hint: If you partition the tasks at positions \(p_0 = 0, p_1, p_2, \ldots, p_m = n\) and denote the prefix sums \(T(i) = \sum_{j=1}^{i} t_j\) and \(F(i) = \sum_{j=1}^{i} f_j\), then the finish time of the batch ending at \(p_r\) is

[ F_r = s \times r + T(p_r), ]

and its cost contribution is

[ F_r \times \Bigl(F(p_r) - F(p_{r-1})\Bigr). ]

Design a dynamic programming solution which considers possible partitions and finds the minimum total cost.

inputFormat

The first line contains two integers n and s (the number of tasks and the machine startup time).

The second line contains n integers: \(t_1, t_2, \ldots, t_n\) (the processing time of each task).

The third line contains n integers: \(f_1, f_2, \ldots, f_n\) (the cost coefficient for each task).

outputFormat

Output a single integer, the minimum total cost to process all tasks.

sample

1 5
10
2

30