这题转化成区间限制权值最大问题，类似于poj3680；我们回顾下吧 orz首先poj3680意思是给出n个区间，每个区间有自己的
权值，使得选出一些区间，使得权值和最大但是不能有点被超过k个区间覆盖。首先，每个权值可以是费用当中用
负值表示，建图方式是首先把所有点按x坐标由小到达排序，于是只看这些点（2*n个，离散下），起点到最左点建容量为
k，cost为0的边，对于每个点都向后面一个点建一个容量为k，cost=0的边，对于每个区间内部，从左端点建一个指向右端点
容量为1（表示只能选一次咯），cost为-w【i】，这样求得的最小费用既是答案。那么看看此题orz首先花费要最少，刚才求的是权值最大那怎么办呢。。。其实花费那就是节约的多，于是可以看怎么弄才能节约最多，对于这m个盒子，如果一个盒子能保持一种颜色从x操作到y操作，他们都是x和y颜色和这个保持的一样，那么就是区间了。所以可以用1个盒子来装入新球，其他m-1个盒子用来省钱用hh，

比如 index： 1 2 3 4 5 6
color: 1 2 3 1 2 3
1号颜色在1和4出现，那么可以转化成刚才那题的1->3区间权值为w[1]，为什么是1->3而不是1->4呢，是因为，走到index=3的时候
把3号求放入那个装新球的特别的盒子的时候，其实顺便可以把这个盒子当成用来省钱的盒子，而那个省钱用的装着1号的盒子就用来装新球了。

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf = (ll)1<<61;
const ll mmax = 200020;
const ll nmax = 200020;

struct Edge
{
    ll u,v,cap,cost,nex;
};
struct Node
{
    ll col,id;
};
Edge e[mmax];
ll n,etot=0;
ll head[nmax];
ll dist[nmax],inq[nmax],pre[nmax],e_used[nmax];
ll nex[nmax];
//pre:最短路前向点 e_used:到i点前一个用过的边
ll max_flow,min_cost=0;
ll w[nmax],a[nmax];
vector<Node> o[nmax];
void init();
void addedge(ll u,ll v,ll cap,ll cost);
bool spfa(ll s,ll t);
void flow_change(ll s,ll t);
void mincost_maxflow(ll s,ll t);
int main()
{
    ll mm,nn,kk,s,t;
    ll all=0;
    init();
    scanf("%lld%lld%lld",&mm,&nn,&kk);
    mm--;
    for(int i=1;i<=nn;i++)
        scanf("%lld",&w[i]);
    for(int i=1;i<=kk;i++)
    {
        scanf("%lld",&a[i]);
    }
    kk=unique(a+1,a+1+kk)-(a+1);
    memset(nex,-1,sizeof(nex));
    for(int i=1;i<=kk;i++)
    {
        if(nex[a[i]]!=-1)
        addedge(nex[a[i]],i-1,1,-w[a[i]]);
        nex[a[i]]=i;
        if(i!=kk)
            addedge(i,i+1,mm,0);
        all+=w[a[i]];
    }
    s=0,t=kk+1;
    n=kk+1;
    addedge(0,1,mm,0);
    addedge(kk,t,mm,0);
    mincost_maxflow(s,t);
    all+=min_cost;
    printf("%lld\n",all);
    return 0;
}

void init()
{
    max_flow=min_cost=0;
    etot=1;
    memset(head,-1,sizeof(head));
}

void addedge(ll u,ll v,ll cap,ll cost)
{
   // cout<<u<<"->"<<v<<"->"<<cap<<"->"<<cost<<endl;
    e[++etot].u=u;
    e[etot].v=v;
    e[etot].cap=cap;
    e[etot].cost=cost;
    e[etot].nex=head[u];
    head[u]=etot;
    e[++etot].u=v;
    e[etot].v=u;
    e[etot].cap=0;
    e[etot].cost=-cost;
    e[etot].nex=head[v];
    head[v]=etot;
}
bool spfa(ll s,ll t)
{
    for(ll i=0; i<=n; i++)dist[i]=inf;
    memset(inq,0,sizeof(inq));
    memset(pre,-1,sizeof(pre));

    queue<ll> q;
    dist[s]=0;
    q.push(s);
    inq[s]=1;

    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        inq[u]=0;
        for(ll i=head[u]; i!=-1; i=e[i].nex)
        {
            ll v=e[i].v;
            if(e[i].cap>0&&dist[v]>dist[u]+e[i].cost)
            {
                dist[v] = dist[u]+e[i].cost;
                pre[v] = u;
                e_used[v] = i;
                if(!inq[v])
                {
                    inq[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}
void flow_change(ll s,ll t)
{
    ll u,f=inf;
    for(u=t; u!=s; u=pre[u])
    {
        f=min(f,e[e_used[u]].cap);
    }
    max_flow+=f;
    for(u=t; u!=s; u=pre[u])
    {
        e[e_used[u]].cap -= f;
        e[e_used[u]^1].cap += f;
        min_cost += f*e[e_used[u]].cost;
    }
}
void mincost_maxflow(ll s,ll t)
{
    while(spfa(s,t))
    {
        flow_change(s,t);
    }
}
/*
这题转化成区间限制权值最大问题，类似于poj3680；
我们回顾下吧 orz
首先poj3680意思是给出n个区间，每个区间有自己的
权值，使得选出一些区间，使得权值和最大但是不能有点
被超过k个区间覆盖。首先，每个权值可以是费用当中用
负值表示，建图方式是首先把所有点按x坐标由小到达排序，
于是只看这些点（2*n个，离散下），起点到最左点建容量为
k，cost为0的边，对于每个点都向后面一个点建一个容量为k，
cost=0的边，对于每个区间内部，从左端点建一个指向右端点
容量为1（表示只能选一次咯），cost为-w【i】，这样求得的
最小费用既是答案。
那么看看此题orz
首先花费要最少，刚才求的是权值最大那怎么办呢。。。其实
花费那就是节约的多，于是可以看怎么弄才能节约最多，对于这
m个盒子，如果一个盒子能保持一种颜色从x操作到y操作，他们都是
x和y颜色和这个保持的一样，那么就是区间了。所以可以用1个盒子
来装入新球，其他m-1个盒子用来省钱用hh，
比如 index： 1 2 3 4 5 6
     color:  1 2 3 1 2 3
1号颜色在1和4出现，那么可以转化成刚才那题的1->3区间权值为
w[1]，为什么是1->3而不是1->4呢，是因为，走到index=3的时候
把3号求放入那个装新球的特别的盒子的时候，其实顺便可以把这个
盒子当成用来省钱的盒子，而那个省钱用的装着1号的盒子就用来装新球了。
*/