#include "lawn.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vvi vector<vi>
#define mii map<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
using namespace std;
void ckmin(int& a, const int& b){a = min(a,b);}
struct Node{
Node *l, *r; int val, lz;
Node(Node *l, Node *r) : l(l), r(r){
val = 4e18; if(l)val = min(val, l->val); if(r)val = min(val, r->val); lz = 0;
}
Node(int x){
val = x; l = nullptr; r = nullptr; lz = 0;
}
void pull(){
val = 4e18; if(l)val = min(val, l->val); if(r)val = min(val, r->val);
}
void add(int x){
val += x; lz += x;
}
};
struct segtree{
int n; Node *root;
segtree(int x){n = x; root = new Node(1e18); sett(root, 0, n-1, 0, 0);}
void pull(Node* v){
v->pull();
}
void push(Node *v){
if(v->l==nullptr){
v->l = new Node(v->val); v->l->lz = v->lz;
}
else v->l->add(v->lz);
if(v->r==nullptr){
v->r = new Node(v->val); v->r->lz = v->lz;
}
else v->r->add(v->lz);
v->lz = 0;
}
// void build(int v, int l, int r, vi &a){
// if(l == r){
// tree[v] = a[l]; return;
// }
// int mid = l + r >> 1; build(v*2,l,mid,a); build(v*2+1,mid+1,r,a); pull(v);
// }
void update(Node *v, int tl, int tr, int l, int r, int x){
if(tl > r || tr < l)return;
if(tl >= l && tr <= r){v->add(x); return;}
push(v); int tm = tl + tr >> 1;
update(v->l,tl,tm,l,r,x); update(v->r,tm+1,tr,l,r,x);
pull(v);
}
int quer(){
return root->val;
}
void add(int l, int r, int x){
// cout<<l<<' '<<r<<' '<<x<<endl;
update(root,0,n-1,l,r,x);
}
void sett(Node* v, int tl, int tr, int k, int x){
if(tl == tr){
v->val = min(v->val, x); return;
}
push(v); int tm = tl + tr >> 1;
if(tm >= k)sett(v->l, tl, tm, k, x);
else sett(v->r,tm+1,tr,k,x);
pull(v);
}
void pset(int k, int x){
sett(root, 0, n-1, k, x);
}
int gett(Node* v, int tl, int tr, int k){
if(tl == tr)return v->val;
push(v); int tm = tl + tr >> 1;
if(tm >= k)return gett(v->l,tl,tm,k);
else return gett(v->r,tm+1,tr,k);
}
int get(int k){
return gett(root,0,n-1,k);
}
};
long long mow(signed N, signed C, signed B, std::vector<signed> &a, std::vector<signed> &v) {
int c = C, b = B; int d = 0; segtree D = segtree(C); f0r(i, N){
int p = c - (v[i] % c), g = ((v[i] + c - 1) / c) * (a[i] + b); if(p == c)p = 0;
//[0,p-1] -> [d, d + p - 1]
if(p > 0){
if(d + p - 1 < c)D.add(d, d + p - 1, g - b);
else D.add(d, c-1, g-b), D.add(0, (d + p - 1) % c, g - b);
}
//p -> d+p
D.add((d + p) % c, (d+p) % c, g);
//[p+1,c-1] -> [d+p+1, d+c-1]
if(d + c - 1 < c){
D.add(d+p+1,d+c-1,g+a[i]);
}
else if(d+p+1 < c){
D.add(d+p+1,c-1,g+a[i]),D.add(0,(d+c-1)%c,g+a[i]);
}
else{
D.add((d+p+1)%c,(d+c-1)%c,g+a[i]);
}
d += p, d %= c; D.pset(d, D.quer() + b);
}
return D.get(d);
return 0;
/* duipai
vi b; b.pb(0); f0r(i, N)b.pb(A[i]); vi a = b; vi w; w.pb(0); f0r(i, N)w.pb(V[i]); vi v = w;
int ans = 0; vvi dp(N+1, vi(C+1, 4e18)); dp[0][0] = 0;
FOR(i,1,N+1){
f0r(j, C+1){
if(j + v[i] <= C)ckmin(dp[i][j+v[i]], dp[i-1][j] + a[i]);
else{
int d = (v[i] - (C - j)) % C; if(d == 0)d = C; ckmin(dp[i][d], dp[i-1][j] + (v[i] - (C - j) + C - 1) / C * (B + a[i]) + a[i]);
}
}
f0r(j, C+1){
ckmin(dp[i][0], dp[i][j] + B);
}
}
return dp[N][0];
*/
}
