鲜花

题目描述

花店中共有 $m$ 种花，编号为 $1,2,\dots,m$，每种花的数量均无限。

黑大帅准备购买恰好 $n$ 朵花。

对于第 $i$ 种花：

• 第一次购买该种花时，可以获得 $a$ 点喜悦度；
• 已经购买过该种花后，每再购买一朵第 $i$ 种花，可以获得 $b_i$ 点喜悦度。

也就是说，如果 黑大帅 一共购买了 $x$ 朵第 $i$ 种花，其中 $x\ge1$，那么这些花产生的总喜悦度为

$a+(x-1)\times b_i$。

黑大帅可以自由决定每种花购买多少朵，但购买的花朵总数必须恰好为 $n$。

请你求出黑大帅能够获得的最大喜悦度。

输入格式

第一行包含三个整数 $m,n,a$，分别表示花的种类数、需要购买的花朵数量，以及第一次购买任意一种花时获得的喜悦度。

第二行包含 $m$ 个整数 $b_1,b_2,\dots,b_m$，其中 $b_i$ 表示再次购买第 $i$ 种花时，每朵花能够获得的喜悦度。

输出格式

输出一行一个整数，表示购买恰好 $n$ 朵花能够获得的最大喜悦度。

样例输入 #1

4 5 3
1 2 3 4

样例输出 #1

19

样例解释1

黑大帅 $5$ 朵花全部购买第 $4$ 种花，获得的喜悦度为：$3+4\times(4)=19$。不存在另外一种方案，使得获得的喜悦度大于 $19$。

样例输入 #2

4 6 7
3 6 4 5

样例输出 #2

40

样例解释2

黑大帅分别购买第 $1,3,4$ 种花各 $1$ 朵，购买第 $2$ 种花 $3$ 朵，获得的喜悦度为：$7+7+7+7+6\times2=40$。不存在另外一种方案，使得获得的喜悦度大于 $40$。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le m\le10^5$；
• $1\le n\le10^6$；
• $1\le a\le10^5$；
• $1\le b_i\le10^5$。

• 特殊性质 A：保证对于所有 $1\le i\le m$，均有 $b_i\le a$。
• 特殊性质 B：保证 $m=1$。
• 特殊性质 C：保证所有 $b_i$ 均相等。