题目描述

农夫 John 建了一个沙滩城堡！城堡的上面有一些城头墙垛（中间是空隙可作为炮口），如下图所示。城堡共有 $N$ 个墙垛，编号为 $1 \dots N$；墙垛 $i$ 的高度为 $M_i$；有些墙垛会很高。

现在他想改变一下墙垛的高度，想把高度改成 $B_1$ 到 $B_N$ 这 $N$ 个给定的高度，但次序是可以任意的。完成这件任务是要花钱雇工匠做的。已知提高一单位高度花费为 $X$；降低一单位高度花费 $Y$。John 希望你能帮助他找到一个最好的排列次序，使他花费最少的钱就能完成这个任务。

输入格式

第 $1$ 行：三个整数 $N, X, Y$。

第 $2$ 到 $N+1$ 行：每行两个整数 $M_i$ 和 $B_i$，分别表示城堡第 $i$ 个墙垛的当前高度和目标高度之一。

输出格式

一个整数，表示完成所有高度调整的最小总费用。

样例

3 6 5
3 1
1 2
1 2

11

样例解释

城堡有 $3$ 个墙垛，当前高度分别为 $3, 1, 1$，目标是将它们变为高度 $1, 2, 2$（次序任意）。增加一单位高度的费用为 $6$，降低一单位高度的费用为 $5$。

一种最优方案：

• 把高度为 $3$ 的墙垛降低 $1$ 单位，花费 $5$，变成 $2$；
• 把其中一个高度为 $1$ 的墙垛增加 $1$ 单位，花费 $6$，变成 $2$； 最终高度为 $2, 2, 1$，总费用为 $5 + 6 = 11$。

数据范围与提示

• 对于 $40\%$ 的数据：$N \le 9$；
• 对于 $60\%$ 的数据：$N \le 18$；
• 对于 $100\%$ 的数据：$1 \le N \le 25\,000$，$1 \le M_i, B_i \le 100\,000$，$1 \le X, Y \le 100$。

答案保证在 $32$ 位有符号整数范围内。