#include "lawn.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n, c, b;
vector<int>a, v;
namespace sub1{
const int lim = 201;
int f[lim][lim];
int dp(int i, int rem){
if(i == n){
return 0;
}
int& ans = f[i][rem];
if(ans != -1){
return ans;
}
if(c < rem){
ans = dp(i, rem - c) + a[i] + b;
}
else{
ans = dp(i + 1, v[i + 1]) + a[i] + b;
for(int j = i + 1, sum = a[i], cur = c - rem; j < n; j++){
sum += a[j];
if(cur >= v[j]){
minimize(ans, dp(j + 1, v[j + 1]) + sum + b);
cur -= v[j];
}
else{
minimize(ans, dp(j, v[j] - cur) + sum + b);
break;
}
}
}
return ans;
}
ll solve(){
memset(f, -1, sizeof(f));
v.push_back(0);
return dp(0, v[0]);
}
}
namespace sub2{
vector<vector<ll>>f;
ll dp(int p, int rem){
if(p == n){
return rem == c ? 0 : b;
}
ll& ans = f[p][rem];
if(ans != -1){
return ans;
}
if(v[p] <= rem){
ans = min(dp(p + 1, rem - v[p]) + a[p], dp(p + 1, c) + a[p] + b);
}
else{
int need = (v[p] - rem) / c;
ans = min(dp(p + 1, c - (v[p] - rem - need * c)) + ll(a[p] + b) * (need + 1) + a[p], dp(p + 1, c) + ll(a[p] + b) * (need + 2));
}
return ans;
}
ll solve(){
f.assign(n, vector<ll>(c + 1, -1));
return dp(0, c);
}
}
const ll INF = 1e18;
namespace sub345{
const int lim = 2e5 + 5;
int N;
ll st[lim << 2], lazy[lim << 2], pfv[lim];
void propagate(int id, ll x){
st[id] += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, ll x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void modify(int id, int l, int r, int p, ll x){
if(l == r){
minimize(st[id], x);
return;
}
int m = (l + r) >> 1;
push_down(id);
if(m < p){
modify(id << 1 | 1, m + 1, r, p, x);
}
else{
modify(id << 1, l, m, p, x);
}
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
ll solve(){
memset(st, 0x0f, sizeof(st));
memset(lazy, pfv[0] = 0, sizeof(lazy));
a.insert(a.begin(), -1);
v.insert(v.begin(), -1);
vector<int>mod_pfv = {-1, 0};
for(int i = 1; i <= n; i++){
mod_pfv.push_back((pfv[i] = pfv[i - 1] + v[i]) % c);
}
sort(mod_pfv.begin(), mod_pfv.end());
mod_pfv.resize(unique(mod_pfv.begin(), mod_pfv.end()) - mod_pfv.begin());
N = int(mod_pfv.size()) - 1;
auto compress_id = [&] (int x){
return lower_bound(mod_pfv.begin(), mod_pfv.end(), x) - mod_pfv.begin();
};
modify(1, 1, N, 1, 0);
for(int i = 1; i <= n; i++){
if(v[i] % c > 1){
int need = c - v[i] % c + 1, r = (pfv[i - 1] % c - need + c) % c, l = (pfv[i - 1] % c + 1) % c;
if(l <= r){
update(1, 1, N, compress_id(l), compress_id(r + 1) - 1, a[i] + b);
}
else{
update(1, 1, N, compress_id(l), N, a[i] + b);
update(1, 1, N, 1, compress_id(r + 1) - 1, a[i] + b);
}
}
update(1, 1, N, 1, N, ll(a[i] + b) * (v[i] / c) + a[i]);
int ci1 = compress_id(pfv[i - 1] % c);
update(1, 1, N, ci1, ci1, v[i] % c == 0 ? -a[i] : b);
modify(1, 1, N, compress_id(pfv[i] % c), st[1]);
}
return st[1];
}
}
ll mow(int _n, int _c, int _b, vector<int>& _a, vector<int>& _v){
swap(a, _a);
swap(v, _v);
if(max({n = _n, b = _b, c = _c, *max_element(a.begin(), a.end()), *max_element(v.begin(), v.end())}) <= 200){
return sub1::solve();
}
if(max({n, c, *max_element(v.begin(), v.end())}) <= 5000){
return sub2::solve();
}
return sub345::solve();
}
