#P3399. [Usaco2009 Mar]Sand Castle城堡
[Usaco2009 Mar]Sand Castle城堡
[USACO 2009 Mar] Sand Castle 沙堡
题目描述
约翰用沙子建了一座城堡。城墙上的两个相邻枪眼之间称为一个垛口墙段。城墙共有 个这样的墙段,初始高度为 。
约翰希望调整它们的高度,最终的高度恰好是 的某种排列。将任一墙段升高一个单位需花费 ,降低一个单位需花费 。求满足目标所需的最少花费。
输入格式
从标准输入读入。第一行是三个整数 。接下来 行,第 行两个整数 。
输出格式
向标准输出输出一行一个整数,表示最少总花费。
3 6 5
3 1
1 2
1 2
11
样例解释
将一个高度为 的墙段降为 ,再将一个高度为 的墙段升为 ,总花费为 。
数据范围与约定
,,。本地旧题面给出的答案上界为 。