import java.io.*;
import java.util.*;

public class evacuation_pk_60 {

	class Edge {
		Vertex to;
		int cap, now;
		Edge pair;

		public Edge(Vertex to, int cap) {
			super();
			this.to = to;
			this.cap = cap;
		}

	}

	class Vertex {
		ArrayList<Edge> e;
		boolean isFinish;
		int last;

		Vertex() {
			e = new ArrayList<evacuation_pk_60.Edge>();
			isFinish = false;
			last = -1;
		}
	}

	void solve() throws IOException {
		int n = nextInt();
		int m = nextInt();
		int K = nextInt();
		int T = nextInt();
		if (n * T > 500)
			throw new AssertionError();
		int[] a = new int[m];
		int[] b = new int[m];
		int[] c = new int[m];
		int[] l = new int[m];
		for (int i = 0; i < m; i++) {
			a[i] = nextInt() - 1;
			b[i] = nextInt() - 1;
			l[i] = nextInt();
			c[i] = nextInt();
			
		}
		Vertex[][] v = new Vertex[T + 1][n];
		for (int i = 0; i < n; i++) {
			v[0][i] = new Vertex();
		}
		int time = 0;
		v[0][n - 1].isFinish = true;
		for (int t = 1; t <= T; t++) {
			//System.err.println(".");
			for (int i = 0; i < n; i++) {
				v[t][i] = new Vertex();
				Edge d = new Edge(v[t][i], (int) 1e9);
				Edge r = new Edge(v[t - 1][i], 0);
				if (i == n - 1) {
					d.cap = 0;
					r.cap = (int)1e9;
				}
				d.pair = r;
				r.pair = d;
				v[t - 1][i].e.add(d);
				v[t][i].e.add(r);
			}
			v[t][n - 1].isFinish = true;
			for (int i = 0; i < m; i++) {
				if (t - l[i] < 0)
					continue;
				Edge d = new Edge(v[t][b[i]], c[i]);
				Edge r = new Edge(v[t - l[i]][a[i]], 0);
				d.pair = r;
				r.pair = d;
				v[t - l[i]][a[i]].e.add(d);
				v[t][b[i]].e.add(r);
			}
			while (true) {
				time++;
				int res = dfs(v[0][0], time, (int)1e9);
				K = K - Math.min(K, res);
				if (res == 0)
					break;
			}
			if (K == 0) {
				out.println(t);
				return;
			}
		}
		if (K == 0)
			throw new AssertionError();
		//System.err.println(K);
		out.println(K);
	}

	private int dfs(Vertex v, int time, int cur) {
		//System.err.println("!");
		if (time == v.last)
			return 0;
		v.last = time;
		if (v.isFinish)
			return cur;
		for (int i = 0; i < v.e.size(); i++) {
			if (v.e.get(i).cap - v.e.get(i).now == 0)
				continue;
			int res = dfs(v.e.get(i).to, time, Math.min(cur, v.e.get(i).cap - v.e.get(i).now));
			if (res < 0)
				throw new AssertionError();
			if (res == 0)
				continue;
			v.e.get(i).now += res;
			v.e.get(i).pair.now -= res;
			return res;
		}
		return 0;
	}

	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;

	void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			br = new BufferedReader(new FileReader(new File("evacuation.in")));
			out = new PrintWriter("evacuation.out");

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {
		new evacuation_pk_60().run();
	}

	String nextToken() throws IOException {
		while ((st == null) || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}
}
