#1042. 「USACO 2012.3 Silver」Landscaping

Farmer John 打算修建一座花园，他需要移动不少泥土。

花园由 个花坛组成（），其中花坛 包含 单位的泥土。FJ 希望花坛 包含 单位的泥土，保证 。

为了达到这个目标，他可以做这几件事情：

• 购买一单位的泥土，放在指定的花坛中，费用为 。
• 从任意一个花坛中移走一单位泥土，费用为 。
• 从花坛 运送一单位泥土到花坛 ，费用为 。

请你帮 FJ 计算移动泥土的最小开销。

第一行四个整数 （）。

接下来 行，第 行两个整数 。

输出移动泥土的最小开销。

输入 #1

4 100 200 1 
1 4 
2 3 
3 2 
4 0

输出 #1

210

按下面的方案，最小花费为 ，可以证明不存在开销更小的方案。

• 移除 号花坛的一单位泥土，花费 。
• 将 号花坛的三单位泥土移到 号花坛，花费 。
• 将 号花坛的一单位泥土移到 号花坛，花费 。