题目内容

古建修复工坊接到一段夯土墙的渗水排查任务。工头需要在一次巡检里处理全部渗水点，使墙面残留的渗水量之和尽量小，并把这个最小值报给修复档案。

墙面上从左到右有 $k$ 处渗水点，第 $i$ 处的渗水量是整数 $h_i$。工坊按规程下发了 $u$ 张封堵令和 $v$ 张引流令，每张令牌只能用在一个渗水点上，用过即作废。巡检时，对每一处渗水点必须且只能选下面三种处置之一：

1. 封堵：消耗 1 张封堵令，该点渗水被完全截断，残留水量为 0。
2. 引流：消耗 1 张引流令，按固定幅度 $g$ 把水引走，该点残留水量为 $\max(0,\ h_i-g)$。
3. 暂缓：不使用令牌，该点残留水量仍为 $h_i$。

同一处不能既封堵又引流。请合理分配令牌，使 $k$ 处残留水量之和最小。

渗水点个数 $k$ 满足 $1 \le k \le$ 200000，封堵令张数 $u$ 与引流令张数 $v$ 满足 $0 \le u,v \le k$，引流幅度 $g$ 满足 $1 \le g \le$ 1000000000，各点渗水量满足 $0 \le h_i \le$ 1000000000。

输入描述

第一行四个整数 $k$、$u$、$v$、$g$（$1 \le k \le$ 200000，$0 \le u,v \le k$，$1 \le g \le$ 1000000000），依次表示渗水点数、封堵令张数、引流令张数和引流幅度。

第二行 $k$ 个整数 $h_1,h_2,\dots,h_k$（$0 \le h_i \le$ 1000000000），表示各点渗水量。

输出描述

输出一个整数，即最优分配下的最小残留水量之和。

样例1

输入

4 1 1 5
12 3 9 1

输出

8

说明

渗水量从大到小是 12、9、3、1。封堵令用在 12 上，残留为 0；引流令用在 9 上，残留为 $\max(0,\ 9-5)=4$；剩下 3 和 1 暂缓。总和为 $0+4+3+1=8$。

样例2

输入

3 0 2 10
4 25 6

输出

19

说明

没有封堵令，两张引流令应给最大的两处：25 变成 15，6 变成 0，4 暂缓，总和为 19。

样例3

输入

1 0 0 1
0

输出

0

说明

只有一处渗水量为 0，也没有任何令牌，残留仍为 0。