AT_abc406_g [ABC406G] Travelling Salesman Problem

[problemUrl]: https://atcoder.jp/contests/abc406/tasks/abc406_g 在数轴上，有你和 $N$ 个商人。商人编号为 $1, 2, \ldots, N$。 开始时，你在坐标 $0$ 处，商人 $i$ 在坐标 $X_i$ 处。此外，每个商人都持有一个物品，商人 $i$ 持有的物品记为物品 $i$。 你的目标是按顺序接收物品 $1, 2, \ldots, N$。 你可以按任意顺序重复任意次数以下三种操作： - 你自己移动 $1$ 个单位长度。此操作的成本为 $C$。 - 选择一个商人，让选定的商人移动 $1$ 个单位长度。此操作的成本为 $D$。 - 选择一个商人，设选定的商人为商人 $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$，你是在坐标 $A_i$ 从商人 $i$ 处接收物品的。

**「数据范围」** - $1 \leq N \leq 2 \times 10^5$ - $1 \leq C, D \leq 10^5$ - $-10^5 \leq X_i \leq 10^5$ - 输入的所有值均为整数 **「样例 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$ 的总成本达成目标。