很不錯的一道題 用線段樹優(yōu)化！
學(xué)習(xí)了怎樣插入順序，使得不重復(fù)計(jì)算

看了edwardmj ，還有請教了zlqiszlq93，他幾句話就說得很清楚了....好膜拜！！！！

/*
    題意：N個村在一條直線上，位置為D[i]  現(xiàn)需要建K個站，在村i建站花費(fèi)為C[i]
           在村i的[ D[i]-S[i],D[i]+S[i] ]范圍內(nèi)只要有站，村i就算被覆蓋了
           如果沒被覆蓋需要賠償W[i]  問最小代價
    F[k,i]表示在前i個村建立k個站的最小代價，且村i有站（只考慮前i個的，后面覆蓋不到需要賠償?shù)南炔挥?jì)）
    F[k,i] = min{ F[k-1,j] + W[j,i] } + C[i]   W[j,i]指在j+1到i-1之間的，不能被j且i覆蓋到村的賠償費(fèi)和
    O(KN^2)  K<=100，N<=20000
    
    zlqiszlq93：
    核心思想 就是利用線段樹 動態(tài)的維護(hù)一個最優(yōu)策略 
    令F[i]前i個點(diǎn)且在i有站的代價為多少那么 F[i] = min(F[j])+W(j,i) W(j,i)屬于補(bǔ)貼的錢 
    然后 分析 點(diǎn)p 他需要補(bǔ)貼錢 當(dāng)且僅當(dāng)i不能覆蓋它，且j也不能覆蓋它
    那么 當(dāng)i不能覆蓋他時 給(1,j)+上補(bǔ)貼p的錢 j為最大的不能覆蓋點(diǎn)p的站

    實(shí)現(xiàn)上，如果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]都不一定是單調(diào)的，需要先排序
    first[p]記錄左邊第一個能覆蓋p的站

    虛設(shè)一個第0個站，在第0個站已建立基站，覆蓋0及之前的，代價當(dāng)然為0

    啟示：
    在點(diǎn)i之前插入的W[i]對于以后的ii(ii>i)都是有效的；
    由于st[p],ed[p]不單調(diào)，需先排序；
    虛設(shè)一個F[0]，這樣k=0時，0之后的都是用W[i]，跟k=0的定義符合；
    F[k,i] = min{ F[k-1,j] + W[j,i] } + C[i]
    如果直接枚舉，發(fā)現(xiàn)某些代價W[p]對于(j,i)需要計(jì)算的話，那么對于(jj,i) jj<j 同樣需要計(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個站的代價永遠(yuǎn)都為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];//現(xiàn)F[i]的值是指F[k+1,i]
            }
            for(;p<=N;p++)//把剩下的也插入，使得線段樹現(xiàn)在存的是F[i]+W[i,n+1]，即真正的代價
                segTree.insert(0,first[ed[p].id]-1,W[ed[p].id]);
            ans=min(ans,segTree.Min());//線段樹存的才是真正花費(fèi)
        }
        printf("%d\n",ans);
    }
    return 0;
}