P2945 [USACO09MAR] Sand Castle S

农夫 John 建造了一座沙堡！像所有好的城堡一样，城墙上有垛口，那种由垛口（空隙）和垛堞（填充空间）组成的精巧图案；见下图。他的城堡墙上的 $N(1 \le N \le 25,000)$ 个垛堞被方便地编号为 $1$ 到 $N$；垛堞 $i$ 的高度为 $M_i(1 \le M_i \le 10^5)$；他的垛堞高度常常不同，这与许多其他的不同。 他希望以以下方式修改城堡设计：他有一个从 $B_1$ 到 $B_N(1 \le B_i \le 10^5)$ 的数字列表，并希望将垛堞的高度更改为这些高度 $B_1, \dots, B_N$ 的某种顺序（不一定是给定的顺序或从数据派生的任何其他顺序）。 为此，他雇佣了一些牛工匠来增加和降低垛堞的高度。当然，工匠们要价很高。特别是，他们向 FJ 收取总共 $X(1 \le X \le 100)$ 每单位高度增加的钱和 $Y(1\le Y \le 100)$ 每单位高度减少的钱。 FJ 想知道如果他选择最佳的高度排列，修改他的沙堡的最低可能成本是多少。答案保证适合 $32$ 位有符号整数。 注意：大约 $40\%$ 的测试数据将有 $N \le 9$，大约 $60\%$ 将有 $N \le 18$ 。

输出包括 $2$ 行。 第 $1$ 行：三个用空格分隔的整数：$N$, $X$ 和 $Y$。 第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行包含两个用空格分隔的整数：$M_i$ 和 $B_i$。

第 $1$ 行：一个整数，重建城堡所需的最低成本。

FJ 的城堡起始高度为 $3$, $1$ 和 $1$。他希望将它们的高度更改为 $1$, $2$ 和 $2$，以某种顺序。增加一个单位高度的成本为 $6$，减少一个单位高度的成本为 $5$。 FJ 将第一个垛堞的高度减少 $1$，成本为 $5$（得到高度为 $2$, $1$ 和 $1$ 的垛堞）。然后他为第二个垛堞增加一个单位的高度，成本为 $6$（得到高度为 $2$, $2$ 和 $1$ 的垛堞）。 （由 ChatGPT 4o 翻译）