OI XXX - wag

// https://szkopul.edu.pl/problemset/problem/UtJx9fM6UT2oxXFenSPjiz5C/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;
typedef uint64_t u;
typedef int64_t s;

int d, a, b;
u n;

namespace brut {

u dp[sizik];

void solve() {
    auto f = [](u w, u v) {
        w %= 1001, v %= 1001;
        return (a * w + b * v) % 1001;
    };

    dp[1] = 0;
    for (int x = 2; x <= n; x++) {
        dp[x] = UINT64_MAX;
        u l = 1, r = std::min((x + d) >> 1, x - 1);
        if (x > d) {
            l = (x - d + 1) >> 1;
        }
        l = std::max(l, (u)1);
        for (int i = l; i <= r; i++) {
            dp[x] = std::min(dp[x], dp[i] + dp[x - i] + f(i, x - i));
        }
    }

    std::cout << dp[n] << '\n';
}

} // namespace brut

std::unordered_map<u, u> dp;

int Q(u w, u v) {
    w %= 1001, v %= 1001;
    return (a * w + b * v) % 1001;
}

void calc(s l, s r) {
    if (l <= 0) l = 1;
    if (l == 1) {
        l = 2;
    } else {
        s l1 = (l - d + 1) >> 1, r1 = (r + d) >> 1;
        calc(l1, r1);
    }

    for (s x = l; x <= r; x++) {
        if (dp[x] != 0) continue;
        dp[x] = UINT64_MAX;
        s l1 = 1, r1 = std::min((x + d) >> 1, x - 1);
        if (x > d) {
            l1 = (x - d + 1) >> 1;
        }
        l1 = std::max(l1, (s)1);
        for (s i = l1; i <= r1; i++) {
            dp[x] = std::min(dp[x], dp[i] + dp[x - i] + Q(i, x - i));
        }
    }
}

void solve() {
    std::cin >> n >> d >> a >> b;

    if (n <= 100 * 1000) {
        return brut::solve();
    }

    dp[1] = 0;
    calc(n, n);

    std::cout << dp[n] << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}