const int INF=;

 const int maxn=,maxm=;

 int cnt=,fir[maxn],nxt[maxm],to[maxm];

 int cap[maxm],val[maxm],dis[maxn],path[maxn];

 void add(int a,int b,int c,int v){

     nxt[++cnt]=fir[a];to[cnt]=b;

     cap[cnt]=c;val[cnt]=v;fir[a]=cnt;

 }

 void addedge(int a,int b,int c,int v){

     add(a,b,c,v);

     add(b,a,,-v);

 }

 int S,T;

 int vis[maxn];

 int Spfa(){

     deque<int>q;

     memset(dis,,sizeof(dis));

     memset(vis,,sizeof(vis));

     q.push_front(S);

     dis[S]=;vis[S]=;

     while(!q.empty()){

         int x=q.front();q.pop_front();vis[x]=;

         for(int i=fir[x];i;i=nxt[i])

             if(cap[i]&&dis[x]+val[i]<dis[to[i]]){

                 dis[to[i]]=val[i]+dis[x];

                 path[to[i]]=i;

                 if(vis[to[i]])continue;

                 if(dis[to[i]]<dis[x])

                     q.push_front(to[i]);

                 else

                     q.push_back(to[i]);

                 vis[to[i]]=;

             }

     }

     return dis[T]==dis[T+]?:dis[T];

 }

 int Aug(){

     int p=T,f=INF;

     while(p!=S){

         f=min(f,cap[path[p]]);

         p=to[path[p]^];

     }

     p=T;

     while(p!=S){

         cap[path[p]]-=f;

         cap[path[p]^]+=f;

         p=to[path[p]^];

     }

     return f;

 }

 int MCMF(){

     int ret=,d;

     while(d=Spfa())

         ret+=Aug()*d;

     return ret;

 }

 #include <queue>

 using namespace std;

 const int maxn=;

 const int maxm=;

 const int INF=;

 int n,m,w[maxn],cnt,fir[maxn],to[maxm],nxt[maxm];

 int cap[maxm],val[maxm],path[maxn],vis[maxn],dis[maxn];

 queue<int>q;

 struct Net_Flow{

     Net_Flow(){cnt=;}

     void add(int a,int b,int c,int v){

         nxt[++cnt]=fir[a];cap[cnt]=c;

         to[cnt]=b;val[cnt]=v;fir[a]=cnt;

     }

     void addedge(int a,int b,int c,int v){

         add(a,b,c,v);add(b,a,,-v);

     }

     int Spfa(int S,int T){

         memset(dis,,sizeof(dis));

         q.push(S);vis[S]=;dis[S]=;

         while(!q.empty()){

             int x=q.front();q.pop();vis[x]=;

             for(int i=fir[x];i;i=nxt[i])

                 if(cap[i]&&dis[to[i]]>dis[x]+val[i]){

                     dis[to[i]]=dis[x]+val[i];

                     if(!vis[to[i]])q.push(to[i]);

                     vis[to[i]]=;path[to[i]]=i;

                 }

         }

         return dis[T];

     }

     int Aug(int S,int T){

         int p=T,f=INF;

         while(p!=S){

             f=min(f,cap[path[p]]);

             p=to[path[p]^];

         }p=T;

         while(p!=S){

             cap[path[p]]-=f;

             cap[path[p]^]+=f;

             p=to[path[p]^];

         }

         return f;

     }

     int MCMF(int S,int T){

         int v=,d;

         while((d=Spfa(S,T))!=INF)

             v+=d*Aug(S,T);

         return v;

     }

 }mcmf;