#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
{
int st[MN<<2], te[MN<<2], mid[MN<<2];
ll mn[MN<<2], lz[MN<<2];
void build(int u, int l, int r)
{
st[u]=l; te[u]=r; mid[u]=(st[u]+te[u])>>1;
mn[u]=inf64; lz[u]=0;
if (st[u]<te[u])
{
build(u*2, st[u], mid[u]);
build(u*2+1, mid[u]+1, te[u]);
}
}
void prop(int u)
{
if (!lz[u]) return;
mn[u*2]+=lz[u];
lz[u*2]+=lz[u];
mn[u*2+1]+=lz[u];
lz[u*2+1]+=lz[u];
lz[u]=0;
}
void set(int u, int p, ll x)
{
if (st[u]==te[u])
{
mn[u]=x;
return;
}
prop(u);
if (p<=mid[u]) set(u*2, p, x);
else set(u*2+1, p, x);
mn[u]=min(mn[u*2], mn[u*2+1]);
}
void upd(int u, int l, int r, ll x)
{
if (st[u]==l && te[u]==r)
{
mn[u]+=x;
lz[u]+=x;
return;
}
prop(u);
if (l<=mid[u]) upd(u*2, l, min(r, mid[u]), x);
if (r>mid[u]) upd(u*2+1, max(mid[u]+1, l), r, x);
mn[u]=min(mn[u*2], mn[u*2+1]);
}
ll qry(int u, int p)
{
if (st[u]==te[u]) return mn[u];
prop(u);
if (p<=mid[u]) return qry(u*2, p);
else return qry(u*2+1, p);
}
ll qry(int u, int l, int r)
{
if (st[u]==l && te[u]==r) return mn[u];
prop(u);
ll z=inf64;
if (l<=mid[u]) z=min(z, qry(u*2, l, min(r, mid[u])));
if (r>mid[u]) z=min(z, qry(u*2+1, 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(1, 0, C-1);
seg::set(1, 0, 0);
for (int i=1; i<=N; i++)
{
int cnt=V[i]/C;
seg::upd(1, 0, C-1, B*cnt+A[i]*(cnt+1));
//for (int j=0; j<C; j++) if ((j+pre[i-1])%C>=C-V[i]) seg::upd(1, j, j, B+A[i]);
int L=(C-pre[i])%C, R=C-pre[i-1]-1;
if (L<=R)
{
for (int j=L; j<=R; j++) assert((j+pre[i-1])%C>=C-V[i]);
for (int j=0; j<C; j++) if ((j+pre[i-1])%C>=C-V[i]) assert(L<=j && j<=R);
seg::upd(1, L, R, B+A[i]);
}
else
{
for (int j=L; j<=C-1; j++) assert((j+pre[i-1])%C>=C-V[i]);
for (int j=0; j<=R; j++) assert((j+pre[i-1])%C>=C-V[i]);
for (int j=0; j<C; j++) if ((j+pre[i-1])%C>=C-V[i]) assert(L<=j || j<=R);
seg::upd(1, L, C-1, B+A[i]);
seg::upd(1, 0, R, B+A[i]);
}
ll z=min(seg::qry(1, ((-pre[i])%C+C)%C)-A[i], seg::qry(1, 0, C-1)+B);
seg::set(1, ((-pre[i])%C+C)%C, z);
}
return seg::qry(1, ((-pre[N])%C+C)%C, ((-pre[N])%C+C)%C);
}
