#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 1000500;
const int inf = 0x3f3f3f3f;
struct *** {
	int v, ne, cap, flow, cost, u;
}ed[maxm];
int head[maxn], cnt;
int pre[maxn], dis[maxn];
bool vis[maxn];
int n, m;
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost) {
	ed[cnt].v = v; ed[cnt].cap = cap; ed[cnt].flow = 0; ed[cnt].u = u;
	ed[cnt].cost = cost; ed[cnt].ne = head[u]; head[u] = cnt++;
	ed[cnt].v = u; ed[cnt].cap = 0; ed[cnt].flow = 0; ed[cnt].u = v;
	ed[cnt].cost = -cost; ed[cnt].ne = head[v]; head[v] = cnt++;
}
bool spfa(int st, int en) {
	queue<int>q;
	for (int s = 0; s <= n; s++) {//这里视情况而定
		dis[s] = inf; vis[s] = 0; pre[s] = -1;
	}
	dis[st] = 0;
	vis[st] = 1;
	q.push(st);
	while (q.size()) {
		int u = q.front();q.pop();
		vis[u] = 0;
		for (int s = head[u]; ~s; s = ed[s].ne) {
			int v = ed[s].v;
			if (ed[s].cap > ed[s].flow&&dis[v] > dis[u] + ed[s].cost) {
				dis[v] = dis[u] + ed[s].cost;
				pre[v] = s;
				if (!vis[v]) {
					vis[v] = 1; q.push(v);
				}
			}
		}
	}
	if (pre[en] == -1)return 0;
	return 1;
}
int MinMax(int st, int en, int &cost) {
	int flow = 0;
	cost = 0;
	while (spfa(st, en)) {
		int min = inf;
		for (int s = pre[en]; ~s; s = pre[ed[s ^ 1].v]) {
			if (min > ed[s].cap - ed[s].flow)
				min = ed[s].cap - ed[s].flow;
		}
		for (int s = pre[en]; ~s; s = pre[ed[s ^ 1].v]) {
			ed[s].flow += min;
			ed[s ^ 1].flow -= min;
			cost += ed[s].cost*min;
		}
		flow += min;
	}
	return flow;
}