#include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 #define MAXN 501

 #define MAXM 50001

 #define INF 2147483647

 int S,T,n,m;

 int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array

 bool inq[MAXN];

 int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;

 queue<int>q;

 void Init_MCMF(){memset(first,-,sizeof(first));en=;}

 void AddEdge(const int &U,const int &V,const int &W,const int &C)

 {

     u[en]=U; v[en]=V; cap[en]=W; cost[en]=C;

     next[en]=first[U]; first[U]=en++;

     u[en]=V; v[en]=U; cap[en]=0; cost[en]=-C;

     next[en]=first[V]; first[V]=en++;

 }

 bool Spfa(int &Flow,int &Cost)

 {

     memset(d,0x7f,sizeof(d));

     memset(inq,,sizeof(inq));

     d[S]=; inq[S]=; p[S]=; a[S]=INF; q.push(S);

     while(!q.empty())

       {

           int U=q.front(); q.pop(); inq[U]=;

           for(int i=first[U];i!=-;i=next[i])

             if(cap[i] && d[v[i]]>d[U]+cost[i])

               {

                 d[v[i]]=d[U]+cost[i];

                 p[v[i]]=i;

                 a[v[i]]=min(a[U],cap[i]);

                 if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=;}

               }

       }

     if(d[T]>) return ;

     Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;

     while(U!=S)

       {

           cap[p[U]]-=a[T]; cap[p[U]^]+=a[T];

           U=u[p[U]];

       }

     return ;

 }

 int Mincost()

 {

     int Flow=,Cost=;

     while(Spfa(Flow,Cost));

     return Cost;

 }