Forcing Flow

Photo of pipes by Pam Broviak, CC BY-SA 2.0

You have constructed a zombie-proof survival compound deep in the mountains, consisting of a collection of buildings. The only task remaining is to connect all the buildings with water pipes. Each pipe connects two buildings, and water will be able to flow through the pipe in either direction. You need to build enough pipes so there is a path between any two buildings (possibly via other buildings). Due to local geography, you are only able to build pipes between certain buildings, and each pipe may cost a different amount of money to construct. Also, your pipe construction budget is limited: you don’t have time to go earn more money, so you can only build a network of pipes whose total cost is within your budget.

Once enough pipes are built, the entire system needs to be pressurized in order to force water through the pipes, using a pressure high enough to ensure that water flows through the whole network. Each pipe has a certain minimum required pressure to force water through it (due to things like the angle and radius of the pipe). The pressure required for the entire network is simply the maximum pressure required by any pipe in the network.

The lower the required pressure, the better: lower pressure translates to a lower chance of failure, and lower ongoing maintenance costs. So your goal is to build a pipe network with the lowest possible required pressure, subject to your budget.

Input

The first line of input consists of three space-separated integers: $1 \leq N \leq 500$, the number of buildings; $0 \leq P \leq N(N-1)/2$, the number of potential pipes; and $0 \leq B \leq 10^9$, your total pipe construction budget.

Then follow $P$ lines of input, one for each potential pipe. Each line contains four space-separated integers $a$, $b$, $c$, and $p$, indicating a potential pipe connecting buildings $a$ and $b$, with a construction cost of $c$ and a required pressure $p$. These values satisfy $0 \leq a < b < N$, $0 \leq c \leq 10^5$, and $0 \leq p \leq 10^9$. No two potential pipes connect the same two buildings.

Output

Output a single integer, the required pressure for a minimum-pressure pipe network that connects all the buildings and fits within your construction budget. If it is not possible to build any pipe network connecting all the buildings within your budget, output the string “Stock up on bottled water!”.

4 4 10
0 1 4 8
0 2 1 10
1 2 3 3
2 3 2 7

8

4 4 8
0 1 4 8
0 2 1 10
1 2 3 3
2 3 2 7

10

4 4 5
0 1 4 8
0 2 1 10
1 2 3 3
2 3 2 7

Stock up on bottled water!