【背景描述】在你的帮助下，JC轻松地打败了DZY，夺回了他的GF。但是由于他的一时疏忽，他居然让邪恶的DZY逃走了。为了防止DZY再祸害其他人，他决定大公无私地把DZY抓回来！

【题目描述】DZY顺着交通网逃到了城市B，而JC还停留在原来的城市A，整个交通网有n个城市，城市A是第一个城市，城市B是第n个城市。某些城市之间有m条有向道路连接，JC每通过一条道路i都要花费一定的时间Ti和一定的金钱Wi。而对于一条JC从城市A到城市B的路径我们称之为一个方案，JC为了衡量一个方案的优劣定义了‘花费比’，任何一个方案的花费比为min（Σ(Wi*Ti)/Σ(Ti+Wi)，min(Wi*n/Ti))，（注：i为方案中JC经过的道路，如果一条道路JC经过了p次，则在花费比计算式中就要累加p次）。但是JC是会魔法的，于是他想让自己的前行更快捷方便。JC最多可以使用k次加速魔法，即在经过一条道路i的时候可以将其Ti减半（向下取整）或者Wi加倍，这个效果只是瞬时有效，举例来说就是JC在经过道路i的时候发动了魔法，在下一次经过这个道路的时候这个魔法就失效了，如果要再保持效果就要再次使用魔法。而且对于同一条道路的同一时刻，JC不能同时发动多次魔法，即效果不能叠加！现在，JC想知道他从A到B可以得到的最小花费比是多少。

第一行是三个正整数，n，m，k。接下来m行每行有4个整数描述一条道路i，分别为Fi，Ei，Ti，Wi，表示这条道路间接Fi到Ei，时间Ti，费用Wi。输入保证存在至少一条从A到B的路径。

只输出一个实数表示最大价值比。保留两位小数。如果答案大于10^10则输出"are you mad?"，大数据边权完全随机。

【数据范围】对于30%的数据k=0，n<=5，m<=5

对于60%的数据k<=5，n<=500，m<=2000

对于100%的数据k<=20，n<=7000，m<=200000，边权为小于等于10^6的数