题目描述

Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height M_i (1 <= M_i <= 100,000); his merlons often have varying heights, unlike so many.

He wishes to modify the castle design in the following fashion: he has a list of numbers B_1 through B_N (1 <= B_i <= 100,000), and wants to change the merlon heights to those heights B_1, ..., B_N in some order (not necessarily the order given or any other order derived from the data).

To do this, he has hired some bovine craftsmen to raise and lower the merlons' heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height

reduced.

FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.

Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.

输入格式

* Line 1: Three space-separated integers: N, X, and Y

* Lines 2..N+1: Line i+1 contains the two space-separated integers: M_i and B_i

输出格式

* Line 1: A single integer, the minimum cost needed to rebuild the castle

题目大意

题目翻译：

农夫约翰（Farmer John）建造了一座沙堡！和所有好的城堡一样，沙堡的墙上有垛口（crenellations），这是一种由开口（embrasures，空隙）和垛体（merlons，填充部分）组成的精巧图案；请参见下面的示意图。沙堡城墙上的 $N$ 个垛体（$1 \leq N \leq 25,000$）被依次编号为 $1$ 到 $N$，其中第 $i$ 个垛体的高度为 $M_i$（$1 \leq M_i \leq 100,000$）。与普通垛口设计不同，他的垛体高度往往是变化的。

他希望按照以下方式修改城堡设计：他有一个数列 $B_1, B_2, \dots, B_N$（$1 \leq B_i \leq 100,000$），他希望将垛体的高度调整为这些数值 $B_1, B_2, \dots, B_N$，但顺序可以随意打乱（不一定是给定的顺序或由数据派生出的某种顺序）。

为此，他雇佣了一些工匠来增加或减少垛体的高度。然而，工匠的费用非常高昂。具体来说，工匠会按如下方式收费：

• 每增加 1 个单位高度，需要支付 $X$（$1 \leq X \leq 100$）单位的费用；
• 每减少 1 个单位高度，需要支付 $Y$（$1 \leq Y \leq 100$）单位的费用。

农夫约翰希望知道，如果他选择最佳的高度排列方式（最佳的 $B$ 数列排列），调整沙堡所需的最低费用是多少。答案保证能在 32 位有符号整数范围内表示。

注意：

• 约 $40\%$ 的测试数据满足 $N \leq 9$；
• 约 $60\%$ 的测试数据满足 $N \leq 18$。

3 6 5 
3 1 
1 2 
1 2 

11 

提示

FJ's castle starts with heights of 3, 1, and 1. He would like to change them so that their heights are 1, 2, and 2, in some order. It costs 6 to add a unit of height and 5 to remove a unit of height.

FJ reduces the first merlon's height by 1, for a cost of 5 (yielding merlons of heights 2, 1, and 1). He then adds one unit of height to the second merlon for a cost of 6 (yielding merlons of heights 2, 2, and 1).