I am trying to solve this problem but getting Wrong Answer several times. My Idea was Binary Search the Bandwidth and run Directed Minimum Spanning Tree each time. I am providing the problem and my code below. Anyone please help me on this. Thanks in advance.

Problem::

During 2009 and 2010 ICPC world finals, the contests were webcasted via World Wide Web. Seeing this, some contest organizers from Ajobdesh decided that, they will provide a live stream of their contests to every university in Ajobdesh. The organizers have decided that, they will provide best possible service to them. But there are two problems:

1. There is no existing network between universities. So, they need to build a new network. However, the maximum amount they can spend on building the network is C.

2. Each link in the network has a bandwidth. If, the stream's bandwidth exceeds any of the link's available bandwidth, the viewers, connected through that link can't view the stream.

Due to the protocols used for streaming, a viewer can receive stream from exactly one other user (or the server, where the contest is organized). That is, if you have two 128kbps links, you won't get 256kbps bandwidth, although, if you have a stream of 128kbps, you can stream to any number of users at that bandwidth.

Given C, find the maximum possible bandwidth they can stream.

Input

Input starts with an integer T (≤ 35), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers N, M, C (1 ≤ N ≤ 60, 1 ≤ M ≤ 104, 1 ≤ C ≤ 109), the number of universities and the number of possible links, and the budget for setting up the network respectively. Each university is identified by an integer between 0 and N-1, where 0 denotes the server.

Each of the next M lines contains four integers u, v, b, c (0 ≤ u, v < N, 1 ≤ b, c ≤ 106), describing a possible link from university u to university v, that has the bandwidth of b kbps and of cost c. All links are unidirectional. There can be multiple links between two universities.

Output

For each case, print the case number and the maximum possible bandwidth to stream. If it's not possible, print "impossible". See the samples for details.

Sample Input

3

3 4 300

0 1 128 100

1 2 256 200

2 1 256 200

0 2 512 300

3 4 500

0 1 128 100

1 2 256 200

2 1 256 200

0 2 512 300

3 4 100

0 1 128 100

1 2 256 200

2 1 256 200

0 2 512 300

Output for Sample Input

Case 1: 128 kbps

Case 2: 256 kbps

Case 3: impossible

My Code: http://paste.ubuntu.com/13223544/