题目分析：
首先想一个DP方程，令f[m][n]表示当前在前n个村庄选了m个基站，且第m个基站放在n处的最小值，转移可以枚举上一个放基站的村庄，然后计算两个村庄之间的代价。
仔细思考两个基站之间村庄的代价，会发现对于一个村庄，它需要付出代价的时候当且仅当上一个基站控制不到它，下一个基站也控制不到它，所以可以计算使它不付出代价的基站区间，然后在超过这段区间的时候加影响。具体来说就是在线段树上面加w[i]。注意滚动数组。
代码：
#include<bits/stdc++.h>
using namespace std; const int maxn = ;
const int inf = ; int n,k;
int d[maxn],c[maxn],s[maxn],w[maxn];
int l[maxn],r[maxn]; int Minn[][<<],lazy[][<<]; void read(){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++) scanf("%d",&d[i]);
for(int i=;i<=n;i++) scanf("%d",&c[i]);
for(int i=;i<=n;i++) scanf("%d",&s[i]);
for(int i=;i<=n;i++) scanf("%d",&w[i]);
} void push_down(int dd,int now){
if(Minn[dd][now<<] != inf){
Minn[dd][now<<] += lazy[dd][now];
lazy[dd][now<<] += lazy[dd][now];
}
if(Minn[dd][now<<|] != inf){
Minn[dd][now<<|] += lazy[dd][now];
lazy[dd][now<<|] += lazy[dd][now];
}
lazy[dd][now] = ;
} void push_up(int dd,int now){
Minn[dd][now] = min(Minn[dd][now<<],Minn[dd][now<<|]);
} void Modify(int dd,int now,int tl,int tr,int l,int r,int dt){
if(Minn[dd][now] == inf) return;
if(tl >= l && tr <= r){Minn[dd][now]+=dt; lazy[dd][now]+=dt;return;}
if(tl > r || tr < l){return;}
if(lazy[dd][now]) push_down(dd,now);
int mid = (tl+tr)/;
Modify(dd,now<<,tl,mid,l,r,dt);
Modify(dd,now<<|,mid+,tr,l,r,dt);
push_up(dd,now);
} int Query(int dd,int now,int tl,int tr,int l,int r){
if(tl >= l && tr <= r){return Minn[dd][now];}
if(tl > r || tr < l){return inf;}
if(lazy[dd][now]) push_down(dd,now);
int mid = (tl+tr)/;
int ans=min(Query(dd,now<<,tl,mid,l,r),Query(dd,now<<|,mid+,tr,l,r));
push_up(dd,now);
return ans;
} vector <int> g[maxn];
void init(){
for(int i=;i<=n;i++){
int lft = ,rgt = i;
while(lft < rgt){
int mid = (lft+rgt)/;
if(d[i]-d[mid] > s[i]) lft = mid+; else rgt = mid;
}
l[i] = lft; lft = i,rgt = n;
while(lft < rgt){
int mid = (lft+rgt+)/;
if(d[mid]-d[i] > s[i]) rgt = mid-; else lft = mid;
}
r[i] = lft;
}
for(int i=;i<=n;i++){g[r[i]+].push_back(i);}
} void work(){
init(); n++;int ans=;
for(int i=;i<=n;i++){ans += w[i]; Modify(,,,n,i,i,inf);}
for(int j=,od=;j<=k+;j++,od^=){
memset(Minn[od],,sizeof(Minn[od]));
memset(lazy[od],,sizeof(lazy[od]));
int z = c[j];
for(int i=;i<j;i++) z+=c[i],Modify(od,,,n,i,i,inf);
Modify(od,,,n,j,j,z);
int pp = ;
for(int i=;i<=n;i++){
for(int st=;st<g[i].size();st++){
Modify(od^,,,n,,l[g[i][st]]-,w[g[i][st]]);
pp += w[g[i][st]];
}
if(i <= j) continue;
Modify(od,,,n,i,i,min(Query(od^,,,n,,i-),pp)+c[i]);
}
ans = min(ans,Query(od,,,n,n,n));
}
printf("%d",ans);
} int main(){
read();
work();
return ;
}