AT_abc406_g.[ABC406G] Travelling Salesman Problem

在数轴上，有你和 $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$ 的总成本达成目标。