SPOJ in Armenian

Գրաֆլանդիայի N քաղաքներն իրար միացված են N - 1 երկկողմանի մայրուղիներով այնպես, որ կամայական քաղաքից մեկ այլ քաղաք տանող ճիշտ մեկ ճանապարհ կա: Գրաֆլանդիայում երթևեկության կանոնները խիստ են։ i-րդ մայրուղին ունի L_i երկարություն և  այդ մայրուղով պետք է երթևեկել այնպիսի հաստատուն արագությամբ, որ ծախսվի ճիշտ T_i ժամանակ: Դա հարմար է. խցանումներ չեն առաջանում։

Բայց տուրիստը չի ուզում արագ երթևեկել։ Նա ցանկանում է ընտրել K + 1 հատ քաղաք պարունակող ճանապարհ այնպես, որ այդ ճանապարվով երթևեկելիս նրա միջին արագությունը լինի հնարավորինս փոքր:

Տրված են N, K թվերը և բոլոր մայրուղիների նկարագրությունները, պետք է հաշվել տուրիստի հնարավոր ամենափոքր միջին արագությունը:

Մուտք

Մուտքի առաջին տողում տրված են N և K թվերը: Հաջորդ N - 1 տողերից յուրաքանչյուրում տրված է մի մայրուղու նկարագրություն: Մայրուղին նկարագրվում է u, v, l, t ամբողջ թվերի քառյակով, որը նշանակում է, որ այն միացնում է u և v քաղաքները, մայրուղու երկարությունը l է, իսկ այն հատելու ժամանակը՝ t (1 ≤ u ≤ N, 1 ≤ v ≤ N,  0 ≤ l ≤ 10⁴, 0 ≤ t ≤ 10⁴, 0 ≤ K < N, N ≤ 20000):

Թեստերի 50%-ում N≤1000:

Ելք

Արտածել խնդրի պատասխանը 10^-6 ճշտությամբ:

Օրինակ

Մուտքը.
4 2
1 2 7 2
2 4 4 6
2 3 4 3

Ելքը.
0.8888889