We may assume that the operations proceed as follows:

• Move yourself toward merchant \(i\), \(0\) or more times.
• Move merchant \(i\) toward yourself, \(0\) or more times, until their coordinate coincides with yours.
• Receive item \(i\) from merchant \(i\).

If we ignore the computational complexity, the answer can be found as follows:

Let \(dp_{i, j}\) be the total cost required to receive items \(1, 2, \ldots, i\) and end up at coordinate \(j\). We may constrain \(j\) to the range \([-10^5, 10^5]\), and the Dynamic Programming (DP) with \(dp_{i, j} = \min (dp_{i - 1, k} + C|j - k| + D|X_i - j|)\) allows us to find the answer.

To speed it up, we use an idea called slope trick. In slope trick, we manage piecewise linear convex functions appropriately to speed up operations against the functions. (In our problem, the domain of the function is (a finite subset of) \(\mathbb{Z}\), so piecewise-linearity is not so essential.)

Take functions \(f_i\) of domain from \(-10^5\) to \(10^5\) satisfying \(f_i(x) = dp_{i, x}\), and consider how to compute the DP above. For \(f_i(x)\), define a function \(g_i(x) = \min (f_i(y) + C|x-y|)\). Then we have \(f_{i + 1}(x) = g_i(x) + D|X_i - x|\).

We will assert that this can be computed fast by appropriately managing the slopes. Maintain a function \(f\) and incrementally update it so that \(f\) corresponds to \(f_i\) and \(g_i\).

For example, it is sufficient to manage the breakpoints and the slope delta (that is, the coordinates \(x\) with \(f(x - 1) - f(x) \neq f(x) - f(x + 1)\) and the value \(f(x - 1) - 2f(x) + f(x + 1)\)), as well as the value and slope at the left end (i.e., the values \(f(-10^5)\) and \(f(-10^5) - f(-10^5+1)\)).

First, we compute \(g_i\) by constraining the slope of \(f_i\) to \([-C, C]\). For the region where the slope is within \([-C, C]\), \(f_i\) and \(g_i\) has the same value. Outside that, we extend the function with slope \(-C\) or \(C\). Therefore, it is sufficient to remove breakpoints from the left and right (or reduce the slope delta).

To obtain \(g_i\) from \(f_{i+1}\), the slope at point \(X_i\) simply increases by \(2D\). The value \(f(-10^5)\) can be updated naively.

Such updates can be done fast enough using a data structure like std::map in C++. More primitively, it is sufficient to perform binary search on a Fenwick tree.

We could now compute the minimum total cost, but we also have to think about the reconstruction.

Considering the operations when obtaining \(g_i\) from \(f_i\), the reconstruction can be processed in reverse order as follows:

• Let \(x\) be the coordinate where you receive an item from merchant \(i\).
  • If \(f_i\) and \(g_i\) has the same value at point \(x\), we find that you receive an item from merchant \((i-1)\) at coordinate \(x\) too.
  • Otherwise, you receive an item from merchant \((i-1)\) at coordinate closest to \(x\) where \(f_i\) and \(g_i\) have the same value.

This requires fast retrieval of slope at each step and coordinate, which can be done by storing all the history to the data structure mentioned above. For example, when performing an operation for merchant \(i\), we also record that we added \(k\) to the \(j\)-th element of the data structure (like std::map or Fenwick Tree). Then during the reconstruction, we can roll back the operation by subtracting by \(k\).