很不错的一道题 用线段树优化！
学习了怎样插入顺序，使得不重复计算

看了edwardmj ，还有请教了zlqiszlq93，他几句话就说得很清楚了....好膜拜！！！！

/*
    题意：N个村在一条直线上，位置为D[i]  现需要建K个站，在村i建站花费为C[i]
           在村i的[ D[i]-S[i],D[i]+S[i] ]范围内只要有站，村i就算被覆盖了
           如果没被覆盖需要赔偿W[i]  问最小代价
    F[k,i]表示在前i个村建立k个站的最小代价，且村i有站（只考虑前i个的，后面覆盖不到需要赔偿的先不计）
    F[k,i] = min{ F[k-1,j] + W[j,i] } + C[i]   W[j,i]指在j+1到i-1之间的，不能被j且i覆盖到村的赔偿费和
    O(KN^2)  K<=100，N<=20000
    
    zlqiszlq93：
    核心思想 就是利用线段树 动态的维护一个最优策略 
    令F[i]前i个点且在i有站的代价为多少那么 F[i] = min(F[j])+W(j,i) W(j,i)属于补贴的钱 
    然后 分析 点p 他需要补贴钱 当且仅当i不能覆盖它，且j也不能覆盖它
    那么 当i不能覆盖他时 给(1,j)+上补贴p的钱 j为最大的不能覆盖点p的站

    实现上，如果D[p]+S[p]<D[i],那么D[p]+S[p]也会<D[ii]  ii>i
    所以p是不用回退的，在i之前插入的p，对于i来说也是有效的（也是i不能覆盖的），不用再插入
    while(Ed[p]<D[i])
        给(1,j)+W[p]
    这里需要成段加上，用线段树

    D[p]-S[p]及D[p]+S[p]都不一定是单调的，需要先排序
    first[p]记录左边第一个能覆盖p的站

    虚设一个第0个站，在第0个站已建立基站，覆盖0及之前的，代价当然为0

    启示：
    在点i之前插入的W[i]对于以后的ii(ii>i)都是有效的；
    由于st[p],ed[p]不单调，需先排序；
    虚设一个F[0]，这样k=0时，0之后的都是用W[i]，跟k=0的定义符合；
    F[k,i] = min{ F[k-1,j] + W[j,i] } + C[i]
    如果直接枚举，发现某些代价W[p]对于(j,i)需要计算的话，那么对于(jj,i) jj<j 同样需要计算
    就是说代价W[p]很多j都需要加上，所以成段更新
    而直接枚举，是枚举了j然后去找p
    这里是对于每个p考虑需要加上的j，考虑角度不同！！
    考察每个p究竟使得那些j需要加上W[p]
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 20010;
const int INF = 1000000000;

inline int min(int a,int b){return a<b?a:b;}

struct Pos
{
    int id,pos;
    void set(int _id,int _pos)
    {
        id=_id;
        pos=_pos;
    }
    bool operator<(const Pos &B)const
    {
        return pos<B.pos;
    }
};

struct Node
{
    int left,right;
    int Min,delta;
};

struct SegTree
{
    Node nodes[MAXN*4];
    Node *root;

    int Min()
    {
        return root->Min;
    }
    void build(int left,int right,int *ary)
    {
        root=&nodes[1];
        build(1,left,right,ary);
    }
    void insert(int left,int right,int x)
    {
        if(left>right)return;
        insert(1,left,right,x);
    }

    void pushdown(int p)//push p to two sons
    {
        if(nodes[p].left==nodes[p].right||nodes[p].delta==0)return;
        nodes[2*p].delta+=nodes[p].delta;
        nodes[2*p].Min+=nodes[p].delta;
        nodes[2*p+1].delta+=nodes[p].delta;
        nodes[2*p+1].Min+=nodes[p].delta;
        nodes[p].delta=0;
    }
    void update(int p)
    {
        pushdown(p);
        nodes[p].Min=min(nodes[2*p].Min,nodes[2*p+1].Min);        
    }
    void build(int p,int left,int right,int *ary)
    {
        nodes[p].left=left;
        nodes[p].right=right;
        nodes[p].delta=0;
        if(left==right)
        {
            nodes[p].Min=ary[left];
            return ;
        }
        int mid=(left+right)>>1;
        build(2*p,left,mid,ary);
        build(2*p+1,mid+1,right,ary);
        update(p);
    }
    void insert(int p,int left,int right,int x)
    {
        if(left<=nodes[p].left&&nodes[p].right<=right)
        {         
            nodes[p].delta+=x;
            nodes[p].Min+=x;
            return;
        }
        int mid=(nodes[p].left+nodes[p].right)>>1;
        if(left>mid)insert(2*p+1,left,right,x);
        else if(right<=mid)insert(2*p,left,right,x);
        else
        {
            insert(2*p,left,mid,x);
            insert(2*p+1,mid+1,right,x);
        }
        update(p);
    }
};

int F[MAXN];//F[k,n]表示前n个建立k个，且n有建站，使得前n个代价最小
          //注意初始化为INF
int D[MAXN],C[MAXN],S[MAXN],W[MAXN];

SegTree segTree;
Pos st[MAXN],ed[MAXN];
int first[MAXN];

int main()
{
    //freopen("in","r",stdin);
    int N,K;
    while(~scanf("%d%d",&N,&K))
    {
        for(int i=2;i<=N;i++)scanf("%d",&D[i]);
        for(int i=1;i<=N;i++)scanf("%d",&C[i]);
        for(int i=1;i<=N;i++)scanf("%d",&S[i]);
        for(int i=1;i<=N;i++)scanf("%d",&W[i]);
        for(int i=1;i<=N;i++)
        {
            st[i].set(i,D[i]-S[i]);
            ed[i].set(i,D[i]+S[i]);
        }
        sort(st+1,st+1+N);
        sort(ed+1,ed+1+N);
    
        for(int i=1,p=1;i<=N;i++)
        {
            while(p<=N&&st[p].pos<=D[i])
            {
                first[st[p++].id]=i;
            }
        }
        int ans = INF;
        F[0]=0;//在第0个站建立，覆盖前0个站的代价永远都为0
        for(int i=1;i<=N;i++)F[i]=INF;//而这时是前i个站没有建立站也没有赔偿村i的代价，就为INF

        for(int k=0;k<=K;k++)
        {
            int i,p;
            segTree.build(0,N,F);
            for(i=1,p=1;i<=N;i++)
            {
                for(;p<=N&&ed[p].pos<D[i];p++)
                {
                    segTree.insert(0,first[ed[p].id]-1,W[ed[p].id]);
                }
                F[i]=segTree.Min()+C[i];//现F[i]的值是指F[k+1,i]
            }
            for(;p<=N;p++)//把剩下的也插入，使得线段树现在存的是F[i]+W[i,n+1]，即真正的代价
                segTree.insert(0,first[ed[p].id]-1,W[ed[p].id]);
            ans=min(ans,segTree.Min());//线段树存的才是真正花费
        }
        printf("%d\n",ans);
    }
    return 0;
}