Optimize Network

You are given a network of cell towers represented by n nodes and m communication links. Each link connects two towers and is described by four integers: u, v (the towers connected), c (the bandwidth capacity), and d (the distance). Your task is to select exactly n-1 communication links to form a spanning tree such that the total bandwidth capacity is maximized while ensuring that the sum of the distances of the selected links does not exceed a given limit D.

Formally, if we denote the chosen set of links as S, you need to maximize

$$\text{Total Bandwidth} = \sum_{(u,v,c,d) \in S} c \quad \text{subject to} \quad \sum_{(u,v,c,d) \in S} d \le D, \quad |S| = n-1. $$

If it is impossible to select such a spanning tree, output Impossible (without quotes).

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains three integers n m D, where n is the number of cell towers, m is the number of communication links, and D is the maximum total distance allowed.
• The following m lines each contain four integers u v c d, representing a communication link between towers u and v with bandwidth capacity c and distance d.

outputFormat

Output a single line to standard output (stdout):

• The maximum sum of bandwidth capacities of the selected links if a spanning tree with a total distance not exceeding D exists.
• Otherwise, output the string Impossible.

## sample

5 6 20
1 2 15 5
1 3 10 3
1 4 5 7
2 3 7 8
2 5 17 6
4 5 20 4

62