aoj2312:Magical_Girl_Sayaka-chan.cpp

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M,L;
int K[2010];
int S[100010];

int memo[2010][2010];

inline int cost(int l,int r){
    l=K[l];r=K[r];
    if(l>r)swap(l,r);
    return (S[r]-S[l-1])/L;
}

int dfs(int l,int r){
    int t=max(l,r)+1;
    if(t==N-1)return cost(l,t)+cost(r,t);
    int &ret=memo[l][r];
    if(ret!=-1)return ret;
    return ret=min(dfs(t,r)+cost(l,t),dfs(l,t)+cost(r,t));
}

signed main(){
    scanf("%lld%lld%lld",&N,&M,&L);
    rep(i,N)scanf("%lld",&K[i]);
    sort(K,K+N);
    rep(i,M)scanf("%lld",&S[i+1]),S[i+1]+=S[i];

    memset(memo,-1,sizeof(memo));
    printf("%lld\n",dfs(0,0));
    return 0;
}