Maximum Bandwidth Within Budget

You are given a network of n computers and m potential cables connecting them. Each cable is described by four integers: two endpoints, the bandwidth capacity, and its cost. Your task is to determine the maximum total bandwidth that can be achieved by connecting all the computers (i.e. forming a spanning tree) such that the overall cost does not exceed a given budget B.

If it is not possible to connect all the computers within the budget, output -1.

The problem can be mathematically formulated as follows:

Let \(G=(V,E)\) be a graph with \(|V|=n\) and each edge \(e\in E\) has a bandwidth capacity \(b_e\) and a cost \(c_e\). Find a spanning tree \(T\subset E\) such that \[ \sum_{e\in T} c_e \le B \] and maximize \[ \sum_{e\in T} b_e. \]

inputFormat

The first line contains three integers n, m, and B, where n is the number of computers, m is the number of available cables, and B is the budget.

Then m lines follow. Each line contains four integers u v b c where u and v are the endpoints of the cable, b is its bandwidth capacity, and c is its cost.

Input is read from standard input (stdin).

outputFormat

Output a single integer, which is the maximum total bandwidth achievable under the budget constraint, or -1 if it is not possible to connect all computers within the budget.

Output is printed to standard output (stdout).

## sample

4 5 20
1 2 5 4
2 3 6 5
3 4 4 3
1 3 2 6
1 4 3 8

15