Optimal Soil Movement

Farmer John is planning to build a garden composed of N flowerbeds. The i-th flowerbed initially contains \(A_i\) units of soil, and Farmer John wants it to contain \(B_i\) units. Both \(A_i\) and \(B_i\) are integers satisfying \(0 \le A_i, B_i \le 10\), and \(1 \le N \le 100\).

To achieve his goal, he is allowed to perform the following operations:

• Buy one unit of soil and add it to a specified flowerbed at a cost of \(X\) per unit.
• Remove one unit of soil from any flowerbed at a cost of \(Y\) per unit.
• Transport one unit of soil from flowerbed \(i\) to flowerbed \(j\) at a cost of \(Z \times |i-j|\) per unit.

Note that if the cost to transport a unit \(Z|i-j|\) is higher than simply removing it and then buying a new one (i.e. if \(Z|i-j| \ge X+Y\)), then it is better to use removal and purchase. Your task is to compute the minimum total cost to achieve the desired distribution of soil.

Hint: Let \(d_i = A_i - B_i\). If \(d_i > 0\) then flowerbed \(i\) has surplus soil that can either be transported or removed, and if \(d_i < 0\) then flowerbed \(i\) needs soil which can either be met by transporting surplus soil or by buying. For any transfer from flowerbed \(i\) (with surplus) to flowerbed \(j\) (with deficit), the effective cost per unit is \(\min(Z\,|i-j|, X+Y)\).

inputFormat

The first line contains four integers \(N\), \(X\), \(Y\), and \(Z\) separated by spaces.

The second line contains \(N\) integers: \(A_1, A_2, \dots, A_N\).

The third line contains \(N\) integers: \(B_1, B_2, \dots, B_N\).

outputFormat

Output a single integer, representing the minimum total cost to adjust the soil in the flowerbeds to the desired configuration.

sample

3 5 4 3
1 2 3
3 2 1

12