题目内容

你负责将 $n$ 个数据集迁移到新存储平台，第 $i$ 个数据集的大小为 $a_i$（GB）。常规传输下，每 GB 数据需要 $x$ 秒；你还可以使用一条高速专线，它能一次性将整个数据集（无论其大小）上传完毕，且固定耗时 $y$ 秒。由于专线资源限制，在整个迁移过程中最多只能使用 $K$ 次高速专线。假设所有传输操作可以无缝衔接，你需要决定将哪些数据集交给高速专线处理，使得完成全部 $n$ 个数据集的总传输时间最短。

数据集的个数 $n$ 不超过 $40000$，$K$ 不超过 $n$，$x$ 和 $y$ 满足 $1 \le x < y \le 10^8$，每个数据集的大小 $a_i$ 不超过 $10^5$。

输入描述

第一行包含四个整数 $n$、$x$、$y$ 和 $K$，分别表示数据集个数、常规传输每 GB 耗时、高速专线每批耗时以及高速专线的最大可用次数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个数据集的大小。

输出描述

输出一个整数，表示完成所有数据集传输所需的最少总时间。