#define min(a,b) ((a)<(b)?(a):(b))

struct edge
{
        int from , to , cost , flow;
        edge (int f,int t,int c,int flw) : from(f),to(t),cost(c),flow(flw)
        {}
};

const int MAX_NODE = 405;
int flow [MAX_NODE];
int cost [MAX_NODE];
int parent [MAX_NODE];

#define INF (1e9)
vector < edge > edgeList;

int n ; // 3add el nodes

inline void bellman (int src,int sink )
{
        int i,j;
        memset ( flow , 0 , (sizeof (int))*n);
        fill(cost,cost+n,INF);

        parent [src] = -1;
        flow [src] = INF;
        cost [src] = 0;

        for (  i = n-1 ; i > 0 ; i -- )
        {
                bool f = false;
                for (  j = 0 ; j < int(edgeList.size()) ; j ++ )
                {
                        if ( cost[edgeList[j].from] + edgeList[j].cost < cost [edgeList[j].to] && edgeList[j].flow > 0)
                        {
                                //relax
                                cost [edgeList[j].to] = cost[edgeList[j].from] + edgeList[j].cost ;
                                parent[edgeList[j].to] = j;
                                flow[edgeList[j].to] = min ( flow[edgeList[j].from] , edgeList[j].flow ) ;
                                f = true;
                        }
                }
                if ( !f )
                        break;
        }
}

inline void addEdge (int f,int t,int c,int flw)
{
        edge e1( f,t,c,flw);
        edge e2( t,f,-c,0);

        edgeList.push_back(e1);
        edgeList.push_back(e2);
}


//returns (flow,cost)
inline pair<int,int> minCost_maxFlow (int src,int sink)
{
        int totF = 0 ,totC = 0;

        if (src==sink)
                return make_pair(INF,0);

        while(1)
        {
                bellman(src,sink);
                if ( flow[sink] <= 0 ) break;

                for (int cur  = sink ; cur != src ; cur = edgeList[parent[cur]].from )
                {
                        int revInd = (parent[cur] & 1) ? parent [cur] -1 : parent [cur] +1 ;
                        edgeList[parent[cur]].flow -= flow[sink];
                        edgeList[revInd].flow += flow[sink];
                        totC += edgeList[parent[cur]].cost * flow[sink];
                }
                totF += flow[sink];
        }
        return make_pair(totF,totC);
}