设 (f[i,j]) 表示前 i 个村庄建立 j 个基站，且第 i 个村庄有基站的最小花费
则有 (f[i,j]=min_{j-1leq k leq i-1}{f[k,j-1]+Cost(k,i)}) 其中 (Cost(k,i)) 表示第 i ,k 个村庄建有基站，中间没有，所需要补偿的费用
发现转移式中从 j-1 -> j ,我们可以脱去 j 这一维
考虑怎么计算 (Cost(k,i),k< i) 。如果村庄 (a) 产生补偿费，当且仅当它没有被覆盖到，那么我们可以预处理出 **能够覆盖到 (a) 的最小和最大的村庄 (st_a) (ed_a) ** ，当 (i) 覆盖不到 (a) ,也即(i>ed_a) 的时候，就把从 1 到 (st_a-1) 的村庄的 (Cost) 都加上 (w_a)
我们要支持一个区间加的操作，和一个区间取最小值的操作。可用线段树维护(f+Cost) 来实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const MAXN=400000,INF=0x7fffffffffff;
int n,k,d[MAXN],c[MAXN],s[MAXN],w[MAXN],st[MAXN],ed[MAXN];
int tot,h[MAXN],f[MAXN],ans;
struct edge{
int to,next;
}e[MAXN];
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
void add(int u,int x){
e[++tot]=(edge){x,h[u]},h[u]=tot;
}
struct Segment_Tree{
int a[MAXN<<2],L[MAXN<<2],R[MAXN<<2],tag[MAXN<<2];
void build(int x,int l,int r){
L[x]=l,R[x]=r;tag[x]=0;
if(L[x]==R[x]){a[x]=f[l];return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
a[x]=min(a[x<<1],a[x<<1|1]);
return;
}
void pushdown(int x){
if(tag[x]){
a[x<<1]+=tag[x];a[x<<1|1]+=tag[x];
tag[x<<1]+=tag[x];tag[x<<1|1]+=tag[x];
tag[x]=0;
}
return;
}
void change(int x,int l,int r,int v){
if(l>r)return;
if(l<=L[x] && R[x]<=r){
a[x]+=v;
tag[x]+=v;
return;
}
pushdown(x);
int mid=(L[x]+R[x])>>1;
if(l<=mid)change(x<<1,l,r,v);
if(r>mid)change(x<<1|1,l,r,v);
a[x]=min(a[x<<1],a[x<<1|1]);
}
int query(int x,int l,int r){
if(l>r)return INF;
if(l<=L[x] && R[x]<=r){
return a[x];
}
pushdown(x);
int mid=(L[x]+R[x])>>1;
int ans=INF;
if(l<=mid)ans=min(ans,query(x<<1,l,r));
if(r>mid)ans=min(ans,query(x<<1|1,l,r));
a[x]=min(a[x<<1],a[x<<1|1]);
return ans;
}
}Tree;
signed main(){
n=read(),k=read();
for(int i=2;i<=n;i++)d[i]=read();
for(int i=1;i<=n;i++)c[i]=read();
for(int i=1;i<=n;i++)s[i]=read();
for(int i=1;i<=n;i++){w[i]=read();ans+=w[i];}
n++,k++;w[n]=d[n]=INF;
for(int i=1;i<=n;i++){
st[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
ed[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d;
if(d[i]+s[i]<d[ed[i]])ed[i]--;
add(ed[i],i);
}
int now=0;
for(int i=1;i<=n;i++){
f[i]=now+c[i];
for(int j=h[i];j;j=e[j].next){
int to=e[j].to;
now+=w[to];
}
}
f[0]=0;
for(int j=2;j<=k;j++){
Tree.build(1,0,n);
for(int i=1;i<=n;i++){
f[i]=i>=j?Tree.query(1,0,i-1)+c[i]:INF;
for(int x=h[i];x;x=e[x].next){
int to=e[x].to;
Tree.change(1,0,st[to]-1,w[to]);
}
}
ans=min(ans,f[n]);
}
printf("%lld
",ans);
return 0;
}