UVa 10983 - Buy one, get the rest free

// UVa 10983 - Buy one, get the rest free
// binary search + max flow

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

struct edge {
	int from, to, cap, cost, day;
};

typedef long long LL;

struct Edge {
	int from, to, cap, flow, index;
	Edge(int from, int to, int cap, int flow, int index) :
			from(from), to(to), cap(cap), flow(flow), index(index) {
	}
};

struct PushRelabel {
	int N;
	vector<vector<Edge> > G;
	vector<LL> excess;
	vector<int> dist, active, count;
	queue<int> Q;

	PushRelabel(int N) :
			N(N), G(N), excess(N), dist(N), active(N), count(2 * N) {
	}

	void AddEdge(int from, int to, int cap) {
		G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
		if (from == to)
			G[from].back().index++;
		G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
	}

	void Enqueue(int v) {
		if (!active[v] && excess[v] > 0) {
			active[v] = true;
			Q.push(v);
		}
	}

	void Push(Edge &e) {
		int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
		if (dist[e.from] <= dist[e.to] || amt == 0)
			return;
		e.flow += amt;
		G[e.to][e.index].flow -= amt;
		excess[e.to] += amt;
		excess[e.from] -= amt;
		Enqueue(e.to);
	}

	void Gap(int k) {
		for (int v = 0; v < N; v++) {
			if (dist[v] < k)
				continue;
			count[dist[v]]--;
			dist[v] = max(dist[v], N + 1);
			count[dist[v]]++;
			Enqueue(v);
		}
	}

	void Relabel(int v) {
		count[dist[v]]--;
		dist[v] = 2 * N;
		for (int i = 0; i < G[v].size(); i++)
			if (G[v][i].cap - G[v][i].flow > 0)
				dist[v] = min(dist[v], dist[G[v][i].to] + 1);
		count[dist[v]]++;
		Enqueue(v);
	}

	void Discharge(int v) {
		for (int i = 0; excess[v] > 0 && i < G[v].size(); i++)
			Push(G[v][i]);
		if (excess[v] > 0) {
			if (count[dist[v]] == 1)
				Gap(dist[v]);
			else
				Relabel(v);
		}
	}

	LL GetMaxFlow(int s, int t) {
		count[0] = N - 1;
		count[N] = 1;
		dist[s] = N;
		active[s] = active[t] = true;
		for (int i = 0; i < G[s].size(); i++) {
			excess[s] += G[s][i].cap;
			Push(G[s][i]);
		}

		while (!Q.empty()) {
			int v = Q.front();
			Q.pop();
			active[v] = false;
			Discharge(v);
		}

		LL totflow = 0;
		for (int i = 0; i < G[s].size(); i++)
			totflow += G[s][i].flow;
		return totflow;
	}
};

bool operator <(const edge & x, const edge & y) {
	return x.day < y.day;
}

edge edges[1000];
int z[30];

int main() {
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++) {
		int n, d, m;
		scanf("%d%d%d", &n, &d, &m);
		vector<int> search_values;
		for (int i = 0; i < m; i++) {
			scanf("%d%d%d%d%d", &edges[i].from, &edges[i].to, &edges[i].cap,
					&edges[i].cost, &edges[i].day);
			edges[i].from--;
			edges[i].to--;
			search_values.push_back(edges[i].cost);
		}
		int visitors = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d", &z[i]);
			visitors += z[i];
		}
		sort(edges, edges + m);
		search_values.push_back(0);
		sort(search_values.begin(), search_values.end());

		int ini = 0, fin = search_values.size() - 1;
		int sol = -1;
		while (ini <= fin) {
			int mid = (ini + fin) / 2;

			// create graph
			PushRelabel flowing((d + 1) * n + 2);
			for (int i = 0; i < m; i++)
				if (edges[i].cost <= search_values[mid])
					flowing.AddEdge(edges[i].day * n + edges[i].from,
							(edges[i].day + 1) * n + edges[i].to, edges[i].cap);

			for (int i = 0; i < n; i++)
				flowing.AddEdge((d + 1) * n, i, z[i]);
			flowing.AddEdge(d * n + n - 1, (d + 1) * n + 1, visitors);

			for (int i = 0; i < n; i++)
				for (int j = 0; j < d; j++)
					flowing.AddEdge(j * n + i, (j + 1) * n + i, visitors);

			if (visitors == flowing.GetMaxFlow((d + 1) * n, (d + 1) * n + 1)) {
				sol = search_values[mid];
				fin = mid - 1;
			} else
				ini = mid + 1;
		}

		if (sol == -1)
			printf("Case #%d: Impossible\n", t);
		else
			printf("Case #%d: %d\n", t, sol);

	}
	return 0;
}