AT_abc406_g [ABC406G] Travelling Salesman Problem

You and $ N $ merchants stand on a number line. The merchants are numbered $ 1, 2, \ldots, N $ . Initially, you are at coordinate $ 0 $ , and merchant $ i $ is at coordinate $ X_i $ . Each merchant holds one item; the item held by merchant $ i $ is called item $ i $ . Your goal is to receive items $ 1, 2, \ldots, N $ in this order. You may repeat any number of times, in any order, the following three operations: - Move yourself by $ 1 $ . The cost of this operation is $ C $ . - Choose one merchant and move that merchant by $ 1 $ . The cost of this operation is $ D $ . - Choose one merchant, say merchant $ i $ . If you and merchant $ i $ are at the same coordinate, and you have not yet received item $ i $ , then receive item $ i $ from merchant $ i $ . Otherwise, do nothing. The cost of this operation is $ 0 $ . Find the minimum total cost required to achieve the goal. Also, output one possible combination of coordinates at which you receive each item when the total cost is minimized.

The input is given from Standard Input in the following format: > $ N $ $ C $ $ D $ $ X_1 $ $ X_2 $ $ \ldots $ $ X_N $

Output two lines. The first line should contain the minimal total cost required to achieve the goal. The second line should contain $ N $ integers $ A_1, A_2, \ldots, A_N $ separated by spaces. Here, there must exist a sequence of operations that satisfies both of the following conditions: - The goal is achieved, with the minimum possible total cost. - For every integer $ i $ such that $ 1 \leq i \leq N $ , you receive item $ i $ at coordinate $ A_i $ .

### Sample Explanation 1 For example, the following sequence of operations achieves the goal with total cost $ 10 $ : - Move merchant $ 1 $ from coordinate $ 1 $ to $ 0 $ . The cost of this operation is $ 3 $ . - Move merchant $ 2 $ from coordinate $ -1 $ to $ 0 $ . The cost of this operation is $ 3 $ . - Receive item $ 1 $ from merchant $ 1 $ . The cost of this operation is $ 0 $ . - Receive item $ 2 $ from merchant $ 2 $ . The cost of this operation is $ 0 $ . - Move yourself from coordinate $ 0 $ to $ 1 $ . The cost of this operation is $ 2 $ . - Move yourself from coordinate $ 1 $ to $ 2 $ . The cost of this operation is $ 2 $ . - Receive item $ 3 $ from merchant $ 3 $ . The cost of this operation is $ 0 $ . It is impossible to achieve the goal with total cost less than $ 10 $ . ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq C, D \leq 10^5 $ - $ -10^5 \leq X_i \leq 10^5 $ - All input values are integers.