namespace nf//network flow
{
    #define NN 750000
    #define MM 1700000
    inline int min(int a,int b){if(a>b)return b;return a;}
    int ver[NN],next[MM<<1],to[MM<<1],c[MM<<1];
    int source,sink,n,tot=1;
    void addedge(int from,int des,int cap)
    {
		//if(show){printf("from=%d,des=%d,cap=%d\n",from,des,cap);cout<<endl;}
        /*
		if(from==source)printf("addedge <source,%d>,cap=%d\n",des,cap);
        else if(des==sink)printf("addedge <%d,sink>,cap=%d\n",from,cap);
        else printf("addedge <%d,%d>,cap=%d\n",from,des,cap);
		printf("from=%d,des=%d\n",from,des);
		*/
        //++tot;++tot;
        
        next[++tot]=ver[from];to[tot]=des;c[tot]=cap;ver[from]=tot;
        next[++tot]=ver[des];to[tot]=from;c[tot]=0;ver[des]=tot;
        
    }
    int h[NN],vh[NN];long long flow;bool found;
    int isap(int poi,int f)
    {
        if(poi==sink)return f;
        int minh=n-1,uf=f;
        for(int i=ver[poi];i;i=next[i])
        {
            if(c[i]>0)
            {
                if(h[poi]==h[to[i]]+1)
                {
					int tmp=isap(to[i],min(c[i],f));
					f-=tmp;
					c[i]-=tmp;
					c[i^1]+=tmp;
                    if(f==0||h[source]>=n)return uf-f;
                }
                if(h[to[i]]<minh)minh=h[to[i]];
            }
        }
        if(uf==f)
        {
            if(--vh[h[poi]]==0)h[source]=n;
            h[poi]=minh+1;
            vh[h[poi]]++;
        }
        return uf-f;
    }
    long long solve()
    {
        vh[0]=n;
        flow=0;
        while(h[source]<n)
        {
            found=false;
            flow+=isap(source,2100000000);
        }
        return flow;
    }
    #undef NN
    #undef MM
}