城市出行

题目描述

Y 同学计划用 $n$ 天游览一座城市。

第 $i$ 天，Y 同学需要乘坐 $a_i$ 次火车。为了完成行程，他可以购买以下两种车票：

• 单程票：每张价格为 $x$ 元，可以乘坐 $1$ 次火车；
• 单日票：每张价格为 $y$ 元，可以在购买当天不限次数乘坐火车。

单程票和单日票均只能在购买当天使用。对于每一天，Y 同学可以自行决定购买若干张单程票，或者购买一张单日票。

请你计算完成全部行程所需的最小花费。

输入格式

第一行包含三个整数 $n,x,y$，分别表示行程天数、单程票的价格和单日票的价格。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 天需要乘坐火车的次数。

输出格式

输出一行一个整数，表示完成全部行程所需的最小花费。

样例

样例输入 #1

3 4 9
2 3 2

样例输出 #1

25

数据范围与约定

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

• $1\le n,x\le 1000$；
• $1\le y\le 10^6$；
• $1\le a_i\le 10^4$。

• 特殊性质 A：保证 $y\ge a_i\times x$ 对所有 $1\le i\le n$ 均成立。
• 特殊性质 B：保证 $y\le x$。