Background

Translated from NOI SG 2024 Prelim A.Tourist.

Problem Description

You are a tourist, and you want to visit a city in $n$ days.

You have already planned your trip. On day $i$, you need to take the train $a_i$ times.

You learned that there are two types of train tickets:

• Single-ride ticket: pay $x$ yuan to buy one single-ride ticket, which allows you to take the train $1$ time.
• Day pass: pay $y$ yuan to buy one day pass, which allows you to take the train any number of times within one day.

Please find the minimum total cost to buy train tickets.

Input Format

The first line contains three integers $n, x, y$.

The second line contains $n$ integers. The $i$-th integer represents $a_i$.

Output Format

Output one integer in one line, representing the minimum cost.

3 4 9
2 3 2

25

Hint

Sample #1 Explanation

Your trip lasts for $3$ days. A single-ride ticket costs $4$ yuan, and a day pass costs $9$ yuan.

On the first day, buy $2$ single-ride tickets, costing $8$ yuan.

On the second day, buy $1$ day pass, costing $9$ yuan.

On the third day, buy $2$ single-ride tickets, costing $8$ yuan.

The minimum cost is $8 + 9 + 8 = 25$ yuan.

Constraints

For $100\%$ of the testdata, $1 \le n, x \le 1000$, $1 \le y \le 10^6$, $1 \le a_i \le 10^4$.

Translated by ChatGPT 5