#include "lawn.h"
#include <iostream>
#include <cassert>
using namespace std;
using ll=long long;
namespace
{
const int MN=2e5+13;
const ll inf64=1e18;
int N; ll C, B;
ll A[MN], V[MN], pre[MN];
}
namespace seg
{
ll st[MN<<5], te[MN<<5], mid[MN<<5];
ll mn[MN<<5], lz[MN<<5];
int lp[MN<<5], rp[MN<<5], idx=0;
int build(ll l, ll r)
{
int u=++idx;
st[u]=l; te[u]=r; mid[u]=(st[u]+te[u])>>1;
mn[u]=inf64; lz[u]=0;
return u;
}
void build(int u)
{
if (!lp[u]) lp[u]=build(st[u], mid[u]);
if (!rp[u]) rp[u]=build(mid[u]+1, te[u]);
}
void prop(int u)
{
if (!lz[u]) return;
mn[lp[u]]+=lz[u];
lz[lp[u]]+=lz[u];
mn[rp[u]]+=lz[u];
lz[rp[u]]+=lz[u];
lz[u]=0;
}
void set(int u, ll p, ll x)
{
if (st[u]==te[u])
{
mn[u]=x;
return;
}
build(u);
prop(u);
if (p<=mid[u]) set(lp[u], p, x);
else set(rp[u], p, x);
mn[u]=min(mn[lp[u]], mn[rp[u]]);
}
void upd(int u, ll l, ll r, ll x)
{
if (st[u]==l && te[u]==r)
{
mn[u]+=x;
lz[u]+=x;
return;
}
build(u);
prop(u);
if (l<=mid[u]) upd(lp[u], l, min(r, mid[u]), x);
if (r>mid[u]) upd(rp[u], max(mid[u]+1, l), r, x);
mn[u]=min(mn[lp[u]], mn[rp[u]]);
}
ll qry(int u, ll p)
{
if (st[u]==te[u]) return mn[u];
build(u);
prop(u);
if (p<=mid[u]) return qry(lp[u], p);
else return qry(rp[u], p);
}
ll qry(int u, ll l, ll r)
{
if (st[u]==l && te[u]==r) return mn[u];
build(u);
prop(u);
ll z=inf64;
if (l<=mid[u]) z=min(z, qry(lp[u], l, min(r, mid[u])));
if (r>mid[u]) z=min(z, qry(rp[u], max(mid[u]+1, l), r));
return z;
}
}
ll mow(int n, int c, int b, vector<int> &a, vector<int> &v)
{
N=n; C=c; B=b;
for (int i=1; i<=N; i++) A[i]=a[i-1];
for (int i=1; i<=N; i++)
{
V[i]=v[i-1];
pre[i]=(pre[i-1]+V[i])%C;
}
seg::build(0, C-1);
seg::set(1, 0, 0);
for (int i=1; i<=N; i++)
{
ll cnt=V[i]/C;
seg::upd(1, 0, C-1, B*cnt+A[i]*(cnt+1));
if (V[i]%C)
{
int L=(C-pre[i])%C, R=C-pre[i-1]-1;
if (L<=R) seg::upd(1, L, R, B+A[i]);
else
{
seg::upd(1, L, C-1, B+A[i]);
seg::upd(1, 0, R, B+A[i]);
}
}
ll z=min(seg::qry(1, (C-pre[i])%C)-A[i], seg::qry(1, 0, C-1)+B);
seg::set(1, (C-pre[i])%C, z);
}
return seg::qry(1, (C-pre[N])%C);
}
