# The one of Indiana Jones P90688

Warning: This problem has some issue.

The system has detected that this problem may have some issue, as a mistake in its statement or a wrong solution. It should be soon be repaired by its problem setter.

Solution status: C++ . (red languages have some issue).

It is not recommended to try to solve this problem until this warning disapears.

Statement

html

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
Public test cases
• Input

```3
5 Patacoma 15 1200
Patacoma Watapito 10 8000
Watapito Wagamama 6 6000
Patacoma Wogopote 5 6500
Watapito Wogopote 4 7000
Wogopote Wagamama 12 10000
1 Patagama 15 6000
Patagama Wagamama 20 10000
1 Patagama 15 1000
Patagama Wagamama 10 1000
```

Output

```4800 15
Indiana has no treasure.
Indiana has no treasure.
```
• Input

```6
1 Waga 10 1000
Waga Wagamama 10 1000
1 Waga 10 5000
Wagamama Waga 10 10000
3 Waga 40 5000
Waga Wagaba 10 6000
Wagaba Wagaca 10 7000
3 Waga 17 1000
Waga Wagamama 10 2000
Wagamama Waga 20 3000
Waga Wagamama 30 2000
5 Wama 37 1165
Wama Wamaba 98 1978
Wama Wamaca 56 1942
Wamaba Wamaca 97 1565
6 Wama 141 1152
Wama Wamaca 31 1997
Wama Wamaba 67 1761
Wamaba Wagamama 73 1892
Wamaca Wagamama 39 1570
```

Output

```Indiana has no treasure.
5000 10
Indiana has no treasure.
1000 10
Indiana has no treasure.
609 140
```
• Information
Author
Ricardo Martín
Language
English
Translator
Carlos Molina
Original language
Spanish
Other languages
Spanish
Official solutions
C++
User solutions
C++