#P3399. [Usaco2009 Mar]Sand Castle城堡

[Usaco2009 Mar]Sand Castle城堡

[USACO 2009 Mar] Sand Castle 沙堡

题目描述

约翰用沙子建了一座城堡。城墙上的两个相邻枪眼之间称为一个垛口墙段。城墙共有 NN 个这样的墙段,初始高度为 M1,M2,…,MNM_1,M_2,\ldots,M_N。

约翰希望调整它们的高度,最终的高度恰好是 B1,B2,…,BNB_1,B_2,\ldots,B_N 的某种排列。将任一墙段升高一个单位需花费 XX,降低一个单位需花费 YY。求满足目标所需的最少花费。

输入格式

从标准输入读入。第一行是三个整数 N,X,YN,X,Y。接下来 NN 行,第 ii 行两个整数 Mi,BiM_i,B_i。

输出格式

向标准输出输出一行一个整数,表示最少总花费。

3 6 5
3 1
1 2
1 2
11

样例解释

将一个高度为 33 的墙段降为 22,再将一个高度为 11 的墙段升为 22,总花费为 5+6=115+6=11。

数据范围与约定

1≤N≤25 0001\le N\le25\,000,1≤Mi,Bi≤100 0001\le M_i,B_i\le100\,000,1≤X,Y≤1001\le X,Y\le100。本地旧题面给出的答案上界为 2322^{32}。