You are given a connected undirected graph with ~N~ nodes and ~M~ edges, where each edge has a weight ~W_i~ and a value ~C_i~. In one operation you can decrease the weight of some edge ~i~ by ~C_i~, edge weights can be zero or negative. You are to perform at most ~K~ operations, and then choose some connected subgraph of the graph containing all ~N~ nodes (possibly the graph itself). Of all possible ways of doing so, you want to minimize the maximum edge weight of the connected subgraph.

Input Specification

The first line contains ~3~ integers ~N\ (1 \leq N \leq 10^5)~, ~M\ \left(N-1 \leq M \leq min\left(\frac{N(N-1)}{2},2\cdot 10^5\right)\right)~, and ~K\ (0 \leq K \leq 10^9)~.

The next ~M~ lines contain ~4~ integers ~A_i,\ B_i\ (1 \leq A_i,B_i \leq N, A_i \neq B_i),\ W_i\ (1 \leq W_i \leq 10^{18}),\ C_i\ (1 \leq C_i \leq 10^9)~, indicating an undirected edge between ~A_i~ and ~B_i~ with weight ~W_i~ and value ~C_i~. There may be repeated edges.

Output Specification

On one line you are to print the minimum maximum edge weight of the connected subgraph.

Subtasks

Subtask 1 (10%)

~K = 0~

Subtask 2 (30%)

~N \leq 15~

Subtask 3 (60%)

No further constraints.

Sample Input

4 4 5
1 2 2 1
2 3 3 2
3 4 4 3
4 1 1 4

Sample Output

-1