AT_abc406_g [ABC406G] Travelling Salesman Problem

数直線上にあなたと $ N $ 人の商人がいます。商人には $ 1, 2, \ldots, N $ の番号が付けられています。 はじめ、あなたは座標 $ 0 $ におり、商人 $ i $ は座標 $ X_i $ にいます。また、各商人は品物を $ 1 $ つずつ持っており、商人 $ i $ が持っている品物を品物 $ i $ と表記します。 あなたの目的は、品物 $ 1, 2, \ldots, N $ をこの順に受け取ることです。 あなたは、以下の $ 3 $ つの操作を好きな順序で好きな回数繰り返すことができます。 - 自分が $ 1 $ 移動する。この操作にはコストが $ C $ かかる。 - 商人を $ 1 $ 人選び、選んだ商人に $ 1 $ 移動してもらう。この操作にはコストが $ D $ かかる。 - 商人を $ 1 $ 人選び、選んだ商人を商人 $ i $ とする。あなたと商人 $ i $ のいる座標が一致しており、あなたが商人 $ i $ から品物を受け取ったことがない場合、商人 $ i $ から品物 $ i $ を受け取る。そうでない場合、何もしない。この操作にはコストが $ 0 $ かかる。 目的を達成するためにかかるコストの合計の最小値を求めてください。 また、目的を達成するためにかかるコストの合計を最小化したときに各商人から品物を受け取る座標として考えられるもののうちのひとつを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C $ $ D $ $ X_1 $ $ X_2 $ $ \ldots $ $ X_N $

$ 2 $ 行出力せよ。 $ 1 $ 行目には目的を達成するためにかかるコストの合計の最小値を出力せよ。 $ 2 $ 行目には、 $ N $ 個の整数 $ A_1, A_2, \ldots, A_N $ をこの順に空白区切りで出力せよ。ただし、ある操作列が存在し、この操作列において以下の条件がともに満たされているようにせよ。 - 目的を達成しており、目的を達成するという条件のもとコストの合計は最小である。 - $ 1 \leq i \leq N $ なるすべての整数 $ i $ に対して商人 $ i $ から 座標 $ A_i $ で品物を受け取っている。

### Sample Explanation 1 例えば以下のように操作をすることで、コストの合計を $ 10 $ として目的を達成することができます。 - 商人 $ 1 $ に座標 $ 1 $ から座標 $ 0 $ に移動してもらう。この操作にはコストが $ 3 $ かかる。 - 商人 $ 2 $ に座標 $ -1 $ から座標 $ 0 $ に移動してもらう。この操作にはコストが $ 3 $ かかる。 - 商人 $ 1 $ から品物 $ 1 $ を受け取る。この操作にはコストが $ 0 $ かかる。 - 商人 $ 2 $ から品物 $ 2 $ を受け取る。この操作にはコストが $ 0 $ かかる。 - あなたが座標 $ 0 $ から座標 $ 1 $ に移動する。この操作にはコストが $ 2 $ かかる。 - あなたが座標 $ 1 $ から座標 $ 2 $ に移動する。この操作にはコストが $ 2 $ かかる。 - 商人 $ 3 $ から品物 $ 3 $ を受け取る。この操作にはコストが $ 0 $ かかる。 コストの合計を $ 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 $ - 入力される値はすべて整数