///费用流
struct MCMF
{
static const int MAXN = 50100;
static const int MAXM = 5001000;
static const int INF = 0x7FFFFFFF;
static const int INF0X3F = 0x3f3f3f3f;
int n, m, first[MAXN], s, t, sign;
int dist[MAXN], inq[MAXN], pre[MAXN], incf[MAXN];
int max_flow, min_cost;
struct Edge
{
int to, cap, cost, next;
} edge[MAXM * 4];
void init(int l, int r, int ss, int tt)
{
//for(int i = l; i <= r; i++ ){first[i] = -1;}
memset(first, -1, sizeof(first));
s = ss, t = tt, sign = 0;
max_flow = min_cost = 0;
}
void add_edge(int u, int v, int cap, int cost)
{
edge[sign].to = v, edge[sign].cap = cap, edge[sign].cost = cost;
edge[sign].next = first[u], first[u] = sign++;
edge[sign].to = u, edge[sign].cap = 0, edge[sign].cost = -cost;
edge[sign].next = first[v], first[v] = sign++;
}
bool spfa(int s, int t)
{
for(int i = 0; i < MAXN; i++ )
{
dist[i] = INF, inq[i] = 0;
}
queue<int>que;
que.push(s), inq[s] = 1, dist[s] = 0;
incf[s] = INF0X3F;
while(!que.empty())
{
int now = que.front();
que.pop();
inq[now] = 0;
for(int i = first[now]; ~i; i = edge[i].next)
{
int to = edge[i].to, cap = edge[i].cap, cost = edge[i].cost;
if(cap > 0 && dist[to] > dist[now] + cost)
{
dist[to] = dist[now] + cost;
incf[to] = min(incf[now], cap);
pre[to] = i;
if(!inq[to])
{
que.push(to);
inq[to] = 1;
}
}
}
}
return dist[t] != INF;
}
void update(int s, int t)
{
int x = t;
while(x != s)
{
int pos = pre[x];
edge[pos].cap -= incf[t];
edge[pos ^ 1].cap += incf[t];
x = edge[pos ^ 1].to;
}
max_flow += incf[t];
min_cost += dist[t] * incf[t];
}
void minCostMaxFlow(int s, int t)
{
while(spfa(s, t))
{
update(s, t);
}
}
} p;
void solve()
{
/// 0 源点
/// m+m+1 次源点
/// m+m+2 汇点
int n, m, K, W;
scanf("%d %d %d %d", &n, &m, &K, &W);
p.init(0, m+m+2 , 0, m+m+2); ///初始化 l，r，开始点，结束点
/*
* 建图
*/
///权值取负
p.minCostMaxFlow(0, m+m+2);
printf("%d\n", -p.min_cost);
};
