33OJ
登录 注册

#P2945. [USACO09MAR] Sand Castle S

[USACO09MAR] Sand Castle S

题目描述

农夫 John 建造了一座沙堡!像所有好的城堡一样,城墙上有垛口,那种由垛口(空隙)和垛堞(填充空间)组成的精巧图案;见下图。他的城堡墙上的 N(1≤N≤25,000)N(1 \le N \le 25,000) 个垛堞被方便地编号为 11 到 NN;垛堞 ii 的高度为 Mi(1≤Mi≤105)M_i(1 \le M_i \le 10^5);他的垛堞高度常常不同,这与许多其他的不同。

他希望以以下方式修改城堡设计:他有一个从 B1B_1 到 BN(1≤Bi≤105)B_N(1 \le B_i \le 10^5) 的数字列表,并希望将垛堞的高度更改为这些高度 B1,…,BNB_1, \dots, B_N 的某种顺序(不一定是给定的顺序或从数据派生的任何其他顺序)。

为此,他雇佣了一些牛工匠来增加和降低垛堞的高度。当然,工匠们要价很高。特别是,他们向 FJ 收取总共 X(1≤X≤100)X(1 \le X \le 100) 每单位高度增加的钱和 Y(1≤Y≤100)Y(1\le Y \le 100) 每单位高度减少的钱。

FJ 想知道如果他选择最佳的高度排列,修改他的沙堡的最低可能成本是多少。答案保证适合 3232 位有符号整数。

注意:大约 40%40\% 的测试数据将有 N≤9N \le 9,大约 60%60\% 将有 N≤18N \le 18 。

输入格式

输出包括 22 行。

第 11 行:三个用空格分隔的整数:NN, XX 和 YY。

第 22 行到第 N+1N+1 行:第 i+1i+1 行包含两个用空格分隔的整数:MiM_i 和 BiB_i。

输出格式

第 11 行:一个整数,重建城堡所需的最低成本。

3 6 5 
3 1 
1 2 
1 2 

11 

提示

FJ 的城堡起始高度为 33, 11 和 11。他希望将它们的高度更改为 11, 22 和 22,以某种顺序。增加一个单位高度的成本为 66,减少一个单位高度的成本为 55。

FJ 将第一个垛堞的高度减少 11,成本为 55(得到高度为 22, 11 和 11 的垛堞)。然后他为第二个垛堞增加一个单位的高度,成本为 66(得到高度为 22, 22 和 11 的垛堞)。 (由 ChatGPT 4o 翻译)