Description

相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。考虑到实际情况，一辆车加满油能开的时间有限，所以在地图上增加了几个加油站。

地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过k个红绿灯的情况下，最少平均花费多少时间能从起点到终点。保证起点终点和加油站没有红绿灯。

（题目不考虑最坏情况下能否加到油，只考虑平均花费时间的前提下，车能否到达加油站加油）。

Input

第一行输入5个整数n，m，k，limit，cost，表示有n个点m条边，车能开limit长的时间，及加油所花时间cost。

接下来n行输入每个点信息，包括点的名称（带“gas”的为加油站，“start”为起点，“end”为终点），及该点是否有红绿灯，（a，b表示）（若为a=0则表示没有，a表示红灯长，b表示绿灯长）。

接下来m行输入每条边信息，包括边的起点，终点，边的名称，通过该边所花时长。

保证点和边名的长度不大于20，只有大小写字母，数字及‘_’组成。

Output

一行输出最少平均花费时长。

Sample Input

Sample Output

Hint

共14组数据：

其中3组数据，满足n<10，m<20，k<5

另有3组没有红绿灯

所有数据满足n<=10000，m<=20000，k<=10，加油站<=50

答案保留3位小数

Source