#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
    
    struct network_flows
    {
        vector<ll> e;
        vector<ll> pre;
        vector<ll> vis;
        vector<vector<ll> > cw;
        vector<vector<ll> > ce;
        vector<double> f;
        vector<double> u;
        vector<vector<double> > c;
        vector<vector<double> > p;
        deque<ll> q;
        
        void clear_flow()
        {
            e.clear();
            pre.clear();
            vis.clear();
            f.clear();
            u.clear();
        }
        
        void clear_edge()
        {
            clear_flow();
            cw.clear();
            ce.clear();
            c.clear();
            p.clear();
        }
        
        ll size()
        {
            return cw.size();
        }
        
        void set_size(ll size_v)
        {
            clear_edge();
            cw.resize(size_v);
            ce.resize(size());
            c.resize(size());
            p.resize(size());
        }
        
        void add_edge(ll x,ll y,double c_v,double p_v)
        {
            cw[x].push_back(y);
            c[x].push_back(c_v);
            p[x].push_back(p_v);
            ce[y].push_back(cw[x].size()-1);
            cw[y].push_back(x);
            c[y].push_back(0);
            p[y].push_back(-p_v);
            ce[x].push_back(cw[y].size()-1);
        }
        
        void prepare(ll s,ll t)
        {
            clear_flow();
            f.resize(size(),0);
            f[s]=oo_max;
            e.resize(size(),-1);
            u.resize(size(),oo_max);
            u[s]=0;
            pre.resize(size(),-1);
            pre[s]=s;
            vis.resize(size(),0);
        }
        
        ll bfs(ll s,ll t,double &flow,double &cost)
        {
            prepare(s,t);
            for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
            {
                ll now=q.front();
                for (ll i=0;i<cw[now].size();i++)
                    if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
                    {
                        f[cw[now][i]]=min(c[now][i],f[now]);
                        e[cw[now][i]]=i;
                        u[cw[now][i]]=u[now]+p[now][i];
                        pre[cw[now][i]]=now;
                        if (vis[cw[now][i]]==0)
                            vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                    }
            }
            flow=f[t];
            cost=u[t];
            return (pre[t]!=-1);
        }
        
        void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
        {
            double temp_flow,temp_cost;
            while (bfs(s,t,temp_flow,temp_cost))
            {
                for (ll i=t;i!=s;i=pre[i])
                    c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
                flow+=temp_flow;
                if (typ==0)
                    cost+=temp_cost;
                else if (typ==1)
                    cost+=(temp_flow*temp_cost);
            }
        }
    };
};