#line 2 "codex/template/template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3","unroll-loops") #include using namespace std; // macros #line 1 "codex/template/macro.hpp" #define fi first #define se second #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define rep1(a) for(ll i=0;i<(ll)(a);i++) #define rep2(i, a) for(ll i=0;i<(ll)(a);i++) #define rep3(i, a, b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep4(i, a, b, c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(a) for(ll i=(ll)(a)-1;i>=0;i--) #define rrep2(i, a) for(ll i=(ll)(a)-1;i>=0;i--) #define rrep3(i, a, b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--) #define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define fore(...) for(auto&&__VA_ARGS__) #define all(i) begin(i),end(i) #define rall(n) (n).rbegin(),(n).rend() #define ini(...) int __VA_ARGS__;in(__VA_ARGS__) #define inl(...) long long __VA_ARGS__;in(__VA_ARGS__) #define ins(...) string __VA_ARGS__;in(__VA_ARGS__) #define in2(s, t) for (int i = 0; i < (int)s.size(); i++) { in(s[i], t[i]); } #define in3(s, t, u) for (int i = 0; i < (int)s.size(); i++) { in(s[i], t[i], u[i]); } #define in4(s, t, u, v) for (int i = 0; i < (int)s.size(); i++) { in(s[i], t[i], u[i], v[i]); } #define fin(...) { out(__VA_ARGS__);return; } #line 9 "codex/template/template.hpp" // utilities #line 1 "codex/template/util.hpp" namespace Nyan { using ll = long long; using ld = long double; using vi = vector; using vl = vector; using vc = vector; using vs = vector; using vb = vector; using vvi= vector; using vvl= vector; using vvc= vector; using pi = pair; using pl = pair; using vp = vector; template using V = vector; template using VV = vector>; template inline bool chmax(T &a, U b) { return a < b && (a = b, true); } template inline bool chmin(T &a, U b) { return a > b && (a = b, true); } template inline T Max(const vector &v) { return *max_element(begin(v), end(v)); } template inline T Min(const vector &v) { return *min_element(begin(v), end(v)); } template inline long long Sum(const vector &v) { return accumulate(begin(v), end(v), 0LL); } template using maxheap = priority_queue; template using minheap = priority_queue, greater>; constexpr ll MOD = 1000000007; constexpr ll mod = 998244353; constexpr int dx[]{+0, +1, +0, -1, +1, +1, -1, -1}; constexpr int dy[]{+1, +0, -1, +0, +1, -1, -1, +1}; void yes(bool x) { cout << (x ? "yes" : "no") << endl; } void Yes(bool x) { cout << (x ? "Yes" : "No") << endl; } void YES(bool x) { cout << (x ? "YES" : "NO") << endl; } } // namespace Nyan #line 12 "codex/template/template.hpp" // input/output #line 1 "codex/template/io.hpp" namespace Nyan { template ostream &operator<<(ostream &os, pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, vector &v) { for (auto it = v.begin(); it != v.end();) { os << *it << ((++it) != v.end() ? " " : ""); } return os; } template istream &operator>>(istream &is, vector &v) { for (T &e : v) is >> e; return is; } void in() {} template void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout.tie(nullptr); cout << fixed << setprecision(12); cerr << fixed << setprecision(12); } } nyan; } // namespace Nyan #line 15 "codex/template/template.hpp" namespace Nyan { void solve(); } signed main() { Nyan::solve(); } /** * @brief Template(テンプレート) */ #line 2 "code.cpp" void Nyan::solve() { ini(n, k, x); vl a(n); in(a); vvl dp(n+1, vl(2, 0)); rep(i, 1, n + 1) { ll cost = a[i-1]; if (i == 1) { dp[i][0] = cost; dp[i][1] = k + x; } else { dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + cost; dp[i][1] = min(dp[i - 1][0] + (k + x), dp[i - 1][1] + k); } } out(Min(dp.back())); /* * membership per day is k + x yen * extend subscription for a day is k yen * what's the minimum cost for solving all the problems I planned * * ok, so * facts: * * 1) I didn't subscribe yesterday * - if the cost of paying individual problems is greater than k + x, than I'll subscribe, the cost is k + x * - else ? * 2) I subscribed yesterday * - if the cost of paying individual problems is greater than k, than I'll subscribe, the cost is k * * state? I subscribed yesterday / I didn't subscribe yesterday -> minimum yen needed if I subscribe or not today * trans? * dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + ai * dp[i][1] = min(dp[i-1][0] + (k + x), dp[i-1][1] + k); * */ }