Optimal Equipment Installation Cost

An exploration team starts at \((0,0)\) and must reach the destination \((0,y)\). The team carries \(n\) devices numbered from \(1\) to \(n\), with device \(i\) having weight \(m_i\). Each device must be installed at some point on the vertical line \(x=x_i\) (the \(y\) coordinate can be arbitrarily chosen). The devices must be installed in order; that is, device \(i\) cannot be installed until all devices \(1, 2, \ldots, i-1\) have been installed, even if the corresponding \(x\) coordinate is reached. Multiple devices can be installed at the same coordinate.

The cost to move one unit of distance when the team is carrying a total weight \(m\) is given by \(m+M\), where \(M\) is an additional constant cost. The team may choose any route in the plane; note that the vertical coordinate of installation points is free to choose. In order to minimize cost, the team can schedule their route so that all horizontal movements (when devices are still carried) occur with no unnecessary vertical changes, thereby postponing any vertical movement until after the heavy devices are offloaded.

The optimal strategy is to perform all the required horizontal moves at a fixed \(y\) (e.g. \(y=0\)) while delivering the devices, and then, once all devices are installed, to move vertically from \((0,0)\) to \((0,y)\). Thus, the compulsory points to visit (in order) are:

• Start at \((0,0)\).
• Visit \((x_1, 0)\) to install device 1.
• Then visit \((x_2, 0)\) to install device 2, and so on.
• After installing device \(n\) at \((x_n, 0)\), return to \((0,0)\).
• Finally, move vertically from \((0,0)\) to \((0,y)\).

If we let \(S=\sum_{i=1}^{n} m_i\), the cost incurred on each segment is as follows:

• From \((0,0)\) to \((x_1,0)\): cost = \((S+M)*|x_1|\).
• For each \(i=1,2,\ldots, n-1\), from \((x_i,0)\) to \((x_{i+1},0)\): after installing the first \(i\) devices, the remaining weight is \(S-\sum_{j=1}^{i}m_j\), so the cost = \(\Big((S-\sum_{j=1}^{i}m_j)+M\Big)*|x_{i+1}-x_i|\).
• From \((x_n,0)\) back to \((0,0)\): cost = \(M*|x_n|\) (since all devices have been installed and only the constant cost applies).
• Finally, moving vertically from \((0,0)\) to \((0,y)\) costs \(M*|y|\) (again, no devices are carried).

The objective is to compute the minimum total cost which is given by:

[ \text{Total Cost} = (S+M),|x_1| + \sum_{i=1}^{n-1} \Big((S-\sum_{j=1}^{i}m_j)+M\Big),|x_{i+1}-x_i| + M,|x_n| + M,|y|. ]

Input Format: The first line contains three integers \(n\), \(M\) and \(y\). The second line contains \(n\) integers \(m_1, m_2, \ldots, m_n\). The third line contains \(n\) integers \(x_1, x_2, \ldots, x_n\). It is guaranteed that \(n \ge 1\) and that there are at least three test cases.

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

inputFormat

Input begins with a line containing three integers: \(n\) (the number of devices), \(M\) (the constant cost), and \(y\) (the final vertical coordinate). The next line contains \(n\) space-separated integers \(m_1, m_2, \ldots, m_n\), representing the weights of the devices. The following line contains \(n\) space-separated integers \(x_1, x_2, \ldots, x_n\) representing the required \(x\)-coordinates where the devices must be installed.

outputFormat

Output a single integer which is the minimum cost for the team to complete all device installations and reach the final destination \((0,y)\).

sample

3 1 10
1 2 3
2 3 1

39