G - Travelling Salesman Problem

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

You and N merchants stand on a number line. The merchants are numbered $1,2,…,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,…,N$ in this order. You may repeat any number of times, in any order, the following three operations:

1. Move yourself by 1. The cost of this operation is C.

2. Choose one merchant and move that merchant by 1. The cost of this operation is D.

3. 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.

Constraints

$1≤N≤2×10^5$

$1≤C,D≤10^5$

$−10^5 ≤X i​ ≤10^5$

All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $C$ $D$

$X_1$ $X_2$ $…$ $X_N$ ​

Output

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 ,…,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≤i≤N$, you receive item i at coordinate $A_i$ .

Sample Input 1

3 2 3
1 -1 2

Sample Output 1

10
0 0 2

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.

Sample Input 2

2 100000 60000
100000 -100000

Sample Output 2

12000000000
0 0

Sample Input 3

6 4 4
2 -1 5 -2 -2 2

Sample Output 3

56
0 -1 -1 -2 -2 2