设f[i][j]表示在第i个村庄建第j个基站的花费
那么有$f[i][j]=min\{f[k][j-1]+w[k,i]\}$，其中w[k,i]表示在k,i建基站，k,i中间的不能被满足的村庄的赔偿金之和
如果把每个村庄能被满足的区间处理出来，记做$[l_i,r_i]$，那么i,j不能满足的村庄，就是$i<l,r<j$的村庄
考虑将$f[i][k]+w[i,j]$的i固定，而j随着dp进行而变化，这样维护K个线段树
那么当j越来越大，会有更多的村庄[l,r]变得满足r<j，被加入到线段树的区间[1,l-1]中
用堆来维护这些村庄，按r从大到小排序即可
复杂度$O(nklogn)$
#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
using namespace std;
typedef long long ll;
const int maxn=2e4+,maxk=; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} int N,K,f[maxn][maxk],pos[maxn],cost[maxn];
struct Node{
int l,r,w;
}p[maxn];
int mi[maxk*maxn*],laz[maxk*maxn*],ch[maxk*maxn*][],rt[maxk],pct;
inline bool operator < (Node a,Node b){return a.r>b.r;}
priority_queue<Node> q; inline void tag(int p,int v){
mi[p]+=v,laz[p]+=v;
} inline void pushdown(int p){
if(!laz[p]) return;
int a=ch[p][],b=ch[p][];
if(a) tag(a,laz[p]);
if(b) tag(b,laz[p]);
laz[p]=;
}
inline void update(int p){
mi[p]=min(mi[ch[p][]],mi[ch[p][]]);
} inline void add(int p,int l,int r,int x,int y,int z){
if(x<=l&&r<=y) tag(p,z);
else{
pushdown(p);int m=l+r>>;
if(x<=m) add(ch[p][],l,m,x,y,z);
if(y>=m+) add(ch[p][],m+,r,x,y,z);
update(p);
}
} inline int query(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return mi[p];
int m=l+r>>;pushdown(p);int re=1e9;
if(x<=m) re=query(ch[p][],l,m,x,y);
if(y>=m+) re=min(re,query(ch[p][],m+,r,x,y));
return re;
} inline void change(int p,int l,int r,int x,int y){
if(l==r) mi[p]=y;
else{
int m=l+r>>;pushdown(p);
if(x<=m) change(ch[p][],l,m,x,y);
else change(ch[p][],m+,r,x,y);
update(p);
}
} inline void build(int &p,int l,int r){
p=++pct;mi[p]=1e9+;
if(l<r){
int m=l+r>>;
build(ch[p][],l,m);build(ch[p][],m+,r);
}
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),K=rd();
for(i=;i<=N;i++)
pos[i]=rd();
for(i=;i<=N;i++)
cost[i]=rd();
pos[N+]=1e9+;
for(i=;i<=N;i++){
int s=rd();
p[i].l=lower_bound(pos+,pos+N+,pos[i]-s)-pos;
p[i].r=upper_bound(pos+,pos+N+,pos[i]+s)-pos-;
}
for(i=;i<=N;i++)
p[i].w=rd();
p[N+].l=N+,p[N+].r=N+,p[N+].w=,N++,K++;
CLR(f,);f[][]=;
for(i=;i<=K;i++) build(rt[i],,N);
for(i=;i<=N;i++){
while(!q.empty()){
Node p=q.top();
if(p.r>=i) break;
q.pop();f[][]+=p.w;
for(k=;k<=min(p.l-,K);k++)
add(rt[k],,N,,p.l-,p.w);
}
f[i][]=f[][]+cost[i];change(rt[],,N,i,f[i][]);
for(k=;k<=min(i,K);k++){
f[i][k]=query(rt[k-],,N,,i-)+cost[i];
change(rt[k],,N,i,f[i][k]);
}
q.push(p[i]);
}
int ans=2e9;
for(i=;i<=K;i++) ans=min(ans,f[N][i]);
printf("%d\n",ans);
return ;
}