Batch Task Processing Cost Minimization

You are given a machine that needs to process (n) tasks in sequence. The tasks are numbered from (1) to (n) and are processed in contiguous batches. Before processing each batch, the machine requires a startup time of (s). The processing time for a task (i) is (T_i) and if tasks from (j+1) to (i) form a batch, then the processing time for the batch is (\sum_{k=j+1}^{i} T_k); however, note that a startup time (s) is incurred at the beginning of every batch. All tasks in the same batch finish at the same time. That is, if batch (X) follows optimally completed tasks up to (j) with finishing time (F_j), then the finishing time for batch (X) is [ F = F_j + s + \sum_{k=j+1}^{i} T_k, ] and each task (k) in that batch incurs a cost of [ \text{cost}_k = F \times C_k, ] where (C_k) is its cost coefficient.

Your goal is to decide how to partition the tasks into batches (each batch consisting of contiguous tasks) so that the total cost is minimized. The total cost is the sum of the costs of all tasks.

For example, if all tasks are processed in one batch then the finishing time is (s + \sum_{i=1}^{n} T_i) and the total cost is ((s + \sum_{i=1}^{n} T_i) \times (\sum_{i=1}^{n} C_i)). However, by splitting into several batches, you might achieve a lower total cost.

Determine the minimum total cost that can be achieved by optimally partitioning the tasks.

inputFormat

The input consists of three lines. The first line contains two integers (n) and (s), where (n) is the number of tasks and (s) is the startup time for each batch. The second line contains (n) integers (T_1, T_2, \ldots, T_n) representing the processing time for each task. The third line contains (n) integers (C_1, C_2, \ldots, C_n) representing the cost coefficient for each task.

outputFormat

Output a single integer — the minimum total cost to process all tasks using an optimal batching strategy.

sample

3 1
1 2 3
3 2 1

25