//-------------------------------------------------------------
// MinCost-MaxFlow
//   O(F E log E)    // F:flow
//   See http://d.hatena.ne.jp/tsukuno/20120320#1332179143
//
// Verified by
//   - (SRM 487 Div2 LV3) in previous version
//   - (SRM 526 Div1 LV1) in previous version
//   - SRM 491 Div1 LV3
//-------------------------------------------------------------

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;

template<typename T>
class IdGen
{
	map<T, int> v2id_;
	vector<T>   id2v_;
public:
	int v2id(const T& v) {
		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
		return v2id_[v];
	}
	const T& id2v(int i) const { return id2v_[i]; }
	int size() const { return id2v_.size(); }
};

template<typename Vert, typename Cost, typename Flow, int NV=256>
class MinCostFlow
{
	IdGen<Vert> idgen;

	vector<int> G[NV];
	Flow F[NV][NV];
	Cost C[NV][NV];

public:
	void addEdge( Vert s_, Vert t_, Cost c, Flow f )
	{
		int s = idgen.v2id(s_), t = idgen.v2id(t_);
		G[s].push_back(t);
		G[t].push_back(s);
		C[s][t] = c;
		C[t][s] = -c;
		F[s][t] = f;
		F[t][s] = 0;
	}

	pair<Cost, Flow> calc( Vert s_, Vert t_ )
	{
		const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
		static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
		static const Flow FLOW_INF = 0x7fffffff;

		Cost total_cost = 0;
		Flow total_flow = 0;
		vector<Cost> dist(N, 0); // Distance from S : initially unknown.
		for(;;)
		{
			// Dijkstra : find the "shortest path" from S to T wrt C[][].
			//   C[][] can be <0 so we must be careful. Instead of computing the shortest path directly,
			//   we compute the increase ("delta") from the shortest path in the previous iteration.
			//   Since shortest path cannot decrease, delta is always >=0 when traversing edges.
			//   Smallest delta implies smallest dist[T]+delta[T].
			vector<Cost> delta(N, COST_INF); delta[S] = 0;
			vector<int>  prev(N, -1);

			typedef pair< Cost, pair<int, int> > cedge;
			priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
			Q.push( cedge(0, make_pair(S, S)) );
			while( !Q.empty() ) {
				const cedge e = Q.top(); Q.pop();
				const int u_prev = e.second.first;
				const int u = e.second.second;
				if( prev[u] >= 0 ) // visited
					continue;
				prev[u] = u_prev;

				for(int i=0; i<G[u].size(); ++i) {
					const int  v = G[u][i];
					const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v];
					if( F[u][v]>0 && delta[v]>v_delta )
						Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) );
				}
			}

			// If T is unreachable, finished.
			if( prev[T] < 0 )
				break;

			// Update the distance table.
			for(int u=0; u<N; ++u)
				if( delta[u] != COST_INF )
					dist[u] += delta[u];

			// How much water can flow on the min-cost path?
			Flow f = FLOW_INF;
			for(int u=T; u!=S; u=prev[u])
				f = min(f, F[prev[u]][u]);

			// Run the flow as much as possible
			total_flow += f;
			for(int u=T; u!=S; u=prev[u]) {
				total_cost    += f * C[prev[u]][u];
				F[prev[u]][u] -= f;
				F[u][prev[u]] += f;
			}
		}
		return make_pair(total_cost, total_flow);
	}
};
