Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3263
Immaterial and Missing Power

Time Limit: 8 Seconds      Memory Limit: 32768 KB      Special Judge

Spring has passed by the land of Gensokyo, a reclusive realm in the far east, and the cherry trees have since shred their blossoms. However, the hanami(flower viewing) kept on going, with feasts being hosted day after day with no end in sight. Adding onto that, every time the feast is held, an unknown restless spiritual aura in Gensokyo also increases; however, nothing happens even while the spiritual aura rises, but when the spiritual aura rises, not a single person attempts to stop the feasts. As such, everyone who goes to the feast, be it human or youkai(phantoms), appears to be very suspicious. The truth is that Ibuki Suika, an oni(ogre) who loves drinks, feasts, and competition, uses her ability to control density to gather people to form a banquet. And she scatters herself to become mist to attend it.

Immaterial&MissingPower(pic)

There are N places and M roads in Gensokyo. Suika wants to made Q residents of Gensokyo have a feast at Hakurei Shrine as soon as possible. Each resident will start off from her residence, choose the fastest route and move at speed Vi. What's more, residents in Gensokyo prefer to "yukkuri shiteitte ne!"("take it easy!"), resident Ri will spend time Tij playing at place Pj once she gets there, excluding the starting and terminal. However, Suika can use her ability to increase one's Vi by Ai * sqrt(ci). As the limit of her ability, the total sum of ci cannot exceed a given number C.

What's the minimum time that Suika needs to wait for before all residents get to Hakurei Shrine to begin the feast.

Input

There are about 16 cases. Process to the end of file.

Each case begins with 3 integers 1 <= N <= 100, 1 <= M <= 1000, 1 <= Q <= 16. Then N places. Each place is identified by its name whose length is less than 30. Then M roads. Each road is represent by two string Pa, Pb, its two ends, and a real number Dab, the distance. Then Q residents. Each resident contains two strings Xi and Pi, her name and her residence, and 2 + N real numbers, Vi, Ai, Ti1, Ti2, ..., TiN. The case ends with a real number C. All real numbers are in range [0.1, 1000000].

Output

The minimum time on separate lines.

Answer having an absolute or relative error less than 1e-6 will be accepted. You can assume that the answer always exists.

Sample Input

2 2 1
Eientei
Hakurei_Shrine
Hakurei_Shrine Eientei 2.72
Eientei Hakurei_Shrine 3.14
Reisen_Udongein_Inaba Eientei 0.1 0.2 0.3 0.4
1
8 11 9
Hakurei_Shrine
Forest_of_Magic(Marisa's_house)
Forest_of_Magic(Alice's_house)
Misty_Lake
Scarlet_Devil_Mansion
Mayohiga
Poltergeist_Mansion
Hakugyokurou
Hakurei_Shrine      Misty_Lake                      218
Hakurei_Shrine	    Forest_of_Magic(Marisa's_house) 192
Hakurei_Shrine      Forest_of_Magic(Alice's_house)  255
Misty_Lake          Forest_of_Magic(Marisa's_house) 51
Misty_Lake          Forest_of_Magic(Alice's_house)  49
Misty_Lake          Mayohiga                        66
Mayohiga            Forest_of_Magic(Alice's_house)  77
Misty_Lake          Scarlet_Devil_Mansion           221
Poltergeist_Mansion Forest_of_Magic(Alice's_house)  71
Poltergeist_Mansion Hakugyokurou                    73
Hakugyokurou        Scarlet_Devil_Mansion           90
Hakurei_Reimu       Hakurei_Shrine                  0.4 0.1 99 99 99 99 99 99 99 99
Kirisame_Marisa     Forest_of_Magic(Marisa's_house) 0.6 0.2 88 77 66 55 44 33 22 11
Izayoi_Sakuya       Scarlet_Devil_Mansion           0.4 0.3 77 10 10 10 10 10 10 10
Alice_Margatroid    Forest_of_Magic(Alice's_house)  0.4 0.2 66 11 22 33 44 55 66 77
Patchouli_Knowledge Scarlet_Devil_Mansion           0.5 0.3 55 15 15 15 15 15 15 15
Konpaku_Youmu       Hakugyokurou                    0.6 0.1 44 11 13 17 19 23 29 31
Remilia_Scarlet     Scarlet_Devil_Mansion           0.6 0.3 33 99 99 88 88 88 11 11
Saigyouji_Yuyuko    Hakugyokurou                    0.4 0.1 22 31 29 23 19 17 13 11
Hong_Meiling        Scarlet_Devil_Mansion           0.5 0.2 11 22 33 44 55 66 77 88
49

Sample Output

9.06666768697071727374757677787980
484.202020202020202020202020202020

External Links

TeamShanghaiAlice(banner)
Wikipedia
Touhou Wiki


Author: WU, Zejun
Source: ZOJ Monthly, November 2009
Submit    Status