The one of Indiana Jones P90688

Indiana Jones has to carry the jewellery and relics that has stolen from the temple of doom trough the jungle to the airport, to bring them to the different occident museums. However, he barely has fuel in his lorry to cover K kilometres. Indiana knows that the roads of the area have a lot of bridges that take the weight of the lorry by few. For this reason he cannot load all the jewellery that he would like. Indiana knows the distance of each path between two villages of the area and the maximal weight that the bridges of the path take. The shorter roads used to have the weaker bridges. The airport is in the town called Wagamama. Compute the maximal weight of treasure than Indiana can load in his lorry, knowing that its weight is C kilos.

Input

The input will consist of various test data, indicating the number of these in the first line of the input. Each case will start with a line where will be indicated the number 1≤ M≤ 10000 of paths of the map, the name of the city where Indiana Jones is coming back from the temple of doom, the quantity 1≤ K≤ 100000 of kilometres that Indiana can cover with the fuel that his lorry has and its weight 1≤ C≤ 10000 (counting Indiana). The following M lines will be indicated for each path, the two cities that has in its extremes separated by a space, the length of the path in kilometres and the maximal path that their bridges take. The names of the cities will be strings of upppercase and lowercase letters without any strange symbols. In the maps that Indiana Jones has there are not more than 500 cities and the lenghts of each path are less than 1000 kilometres.

Notice (look the test data of instance) that the roads are bidirectional, and that for each pair of cities A and B, can be zero, one or more than a path that link directly.

Output

For each test data, your program must print a line that indicates the maximal weight of the treasure in kilos and, for this quantity of treasure, the minimal distance in kilometres that he would have to cover to arrive to the airport. If Indiana could not arrive to Wagama with the fuel that he has following the paths of the map, or if he could arrive but with a load of treasure of 0 kilos, it must print ’Indiana has no treasure.’ (respecting uppercase and lowecarse letters and the final dot).

Scoring

• TestA:   Tests where all the bridges can take the same weight.  40 Points 

• TestA:   Tests where in any map appears more than 100 cities.  35 Points 

• TestA:   Tests of all kinds.  25 Points