Subtask 1

• Ta thấy rằng việc mua hai viên đá không có ý nghĩa nên là ta chỉ cần mua một viên đá cho đến khi tất cả các chồng bằng với chồng cao nhất thôi.

Subtask 2

• Ta thấy rằng ở subtask này, vị trí mà đạt ít tiền nhất chỉ có thể là giá trị lớn nhất của dãy. Tính chất này độc giả có thể tự chứng minh thêm.

• Để xử lý, ta có thể dùng Heap để lấy chồng cao nhất và thấp nhất.

Subtask 3

• Vì ~N~ và ~A_i~ nhỏ nên ta có thể thử trâu mọi độ cao cuối cùng của chồng đá. Nhưng cận trên ta cần xét là bao nhiêu.

• Ta xét mảng ~A=[0,1000,1000]~ và ~C_1=100000~ còn ~C_2=1~. Ta thấy rằng ta sẽ chỉ mua hai viên đá và cách đặt tối ưu là đặt ở vị trí đầu và luôn phiên vị trí thứ hai và thứ ba. Mảng ~A~ cuối cùng của ta sẽ chỉ là ~A=[2000,2000,2000]~ và đáp án là ~200\,000~. Ta thấy là đây chính là trường hợp tệ nhát nên và độ cao tối ưu là ~2 \times max(A_i)~. Vì thế ta dễ nhận thấy rằng độ cao tối ưu sẽ không quá ~2 \times max(A_i)~ và việc trâu là khả thi.

• Độ phức tạp: ~O(max(A_i) \times N)~.

Subtask 4

• Tối ưu subtask 3, với mỗi độ cao ta tìm tổng chi phí trong ~O(1)~ thay vì ~O(N)~.

• Độ phức tạp: ~O(max(A_i))~.

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 1e5 + 6;
const int MAXM = 1e6 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 9;

int n, c1, c2;
int a[MAXN];

int64_t get1(int lim) {
    int64_t sum = 0;
    for (int i = 1; i <= n; i++) sum += 1LL * (lim - a[i]) * c1;
    return sum;
}

int64_t get2(int aim) {
    priority_queue<int> s;
    for (int i = 1; i <= n; i++) 
        if (aim - a[i] > 0) s.push(aim - a[i]);

    int64_t sum = 0;


    while (sz(s) > 1) {
        int mx1 = s.top();
        s.pop();

        int mx2 = s.top();
        s.pop();

        sum += 1LL * mx2 * c2;

        if ((mx1 - mx2) > 0) s.push(mx1 - mx2);
    }

    while (sz(s)) {
        sum += 1LL * s.top() * c1;
        s.pop();
    }

    return sum;
}

int64_t max_f(int left, int right) {
    int mi = 1e9;
    int64_t sum = 0;
    for (int i = 1; i <= n; i++) {
        mi = min(mi, a[i]);
        sum += left - a[i];
    }
    int64_t res = 8e18;
    for (int i = left; i <= right; i++) {
        int64_t sum2 = sum, ans = 0;
        int ma = i - mi;
        sum2 -= ma;
        if (sum2 < ma) ans = 1ll * c2 * sum2 + 1ll * c1 * (ma - sum2);
        else {
            ans = 1ll * c2 * ma;
            sum2 -= ma;
            ans += 1ll * c2 * (sum2 / 2);
            sum2 &= 1;
            if (sum2) ans += c1;
        }
        res = min(res, ans);
        sum += n;
    }

    return res;
}


void solve() {
    cin >> n >> c1 >> c2;

    int mx = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], maximize(mx, a[i]);


    if (c1 * 2 <= c2) {
        cout << get1(mx);
    }
    else if (c1 <= c2) {
        cout << get2(mx);
    }
    else {
        cout << max_f(mx, mx * 2);
    }
}

#define TASK ""
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;

    while (ntest--) solve();

    return 0;
}
//612