시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 42 22 17 62.963%

문제

N(4≤N≤400)개의 정점과 M(1≤M≤10,000)개의 양방향 간선들이 있다. 그런데 지진이 일어나서 모든 간선들이 끊어져 버렸다. 이제 이 간선들 중 몇 개를 복원하여 임의의 정점에서 다른 임의의 정점으로 이동하는 경로가 존재하도록 만드려고 한다.

복원 비용으로는 F(1≤F≤2,000,000,000)원이 주어져 있다. 각각의 간선들에는 그 간선을 복원하는데 걸리는 시간 t(1≤t≤2,000,000,000)와 그 간선을 복원하는데 필요한 비용 c(1≤c≤2,000,000,000)가 필요하다. 두 정점을 잇는 간선을 복원하는 방법이 여러 가지일 수 있어서, 같은 간선인데 복원 비용이나 시간이 다를 수 있다. 복원 비용이 F를 넘게 되더라도, 복원하는 방법은 항상 존재하도록 입력이 주어진다.

간선들을 복원했을 때, 시간당 얻게 되는 이득이 최대가 되도록 하는 방법을 찾으라.

입력

첫째 줄에는 세 정수 N, M, F가 주어진다. 다음 M개의 줄에는 간선의 정보를 나타내는 i, j, c, t가 주어진다. i, j는 정점의 번호이고, c는 비용, t는 시간이다.

출력

첫째 줄에 시간당 얻게 되는 최대의 이득을 소숫점 아래 넷째 자리까지 출력한다. 만약 이득이 양수가 아니면 0.0000을 출력한다.

예제 입력 1

5 5 100
1 2 20 5
1 3 20 5
1 4 20 5
1 5 20 5
2 3 23 1

예제 출력 1

1.0625

힌트

2, 3, 4, 5번 간선을 복원하는 경우가 최적해이다. 이 때의 총 비용은 83이 되고, 걸리는 시간은 16이 된다. 따라서 이득은 100-83=17원이 되고, 따라서 시간당 얻는 이득은 17/16=1.0625가 된다.

W3sicHJvYmxlbV9pZCI6IjIxMjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWM5YzQiLCJkZXNjcmlwdGlvbiI6IjxwPk4oNCZsZTtOJmxlOzQwMClcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVhY2ZjIE0oMSZsZTtNJmxlOzEwLDAwMClcdWFjMWNcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YWMwNFx1YzEyMFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWM5YzBcdWM5YzRcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWM3NzQgXHViMDRhXHVjNWI0XHVjODM4IFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1Yzc3NCBcdWFjMDRcdWMxMjBcdWI0ZTQgXHVjOTExIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHViY2Y1XHVjNmQwXHVkNTU4XHVjNWVjIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIzYzRcdWI4NWQgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cdWJjZjVcdWM2ZDAgXHViZTQ0XHVjNmE5XHVjNzNjXHViODVjXHViMjk0IEYoMSZsZTtGJmxlOzIsMDAwLDAwMCwwMDApXHVjNmQwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWJjZjVcdWM2ZDBcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNCB0KDEmbGU7dCZsZTsyLDAwMCwwMDAsMDAwKVx1YzY0MCBcdWFkZjggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViZTQ0XHVjNmE5IGMoMSZsZTtjJmxlOzIsMDAwLDAwMCwwMDApXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3YyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWFjMTlcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzc4XHViMzcwIFx1YmNmNVx1YzZkMCBcdWJlNDRcdWM2YTlcdWM3NzRcdWIwOTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJjZjVcdWM2ZDAgXHViZTQ0XHVjNmE5XHVjNzc0IEZcdWI5N2MgXHViMTE4XHVhYzhjIFx1YjQxOFx1YjM1NFx1Yjc3Y1x1YjNjNCwgXHViY2Y1XHVjNmQwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuPHA+XHVhYzA0XHVjMTIwXHViNGU0XHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzJkY1x1YWMwNFx1YjJmOSBcdWM1YmJcdWFjOGMgXHViNDE4XHViMjk0IFx1Yzc3NFx1YjRkZFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjYzNlXHVjNzNjXHViNzdjLjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggTiwgTSwgRlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBpLCBqLCBjLCB0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaSwgalx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBjXHViMjk0IFx1YmU0NFx1YzZhOSwgdFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1YWMwNFx1YjJmOSBcdWM1YmJcdWFjOGMgXHViNDE4XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWM3NzRcdWI0ZGRcdWM3NDQgXHVjMThjXHVjMjJiXHVjODEwIFx1YzU0NFx1Yjc5OCBcdWIxMzdcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Yzc3NFx1YjRkZFx1Yzc3NCBcdWM1OTFcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmM4XHViYTc0IDAuMDAwMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiPHA+MiwgMywgNCwgNVx1YmM4OCBcdWFjMDRcdWMxMjBcdWM3NDQgXHViY2Y1XHVjNmQwXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWNkNWNcdWM4MDFcdWQ1NzRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGNcdWM3NTggXHVjZDFkIFx1YmU0NFx1YzZhOVx1Yzc0MCA4M1x1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMTZcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc0XHViNGRkXHVjNzQwIDEwMC04Mz0xN1x1YzZkMFx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMyZGNcdWFjMDRcdWIyZjkgXHVjNWJiXHViMjk0IFx1Yzc3NFx1YjRkZFx1Yzc0MCAxN1wvMTY9MS4wNjI1XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjEyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVhcnRocXVha2UiLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGVhcnRocXVha2UgaGFzIGRlc3Ryb3llZCBGYXJtZXIgSm9obiYjMzk7cyBlbnRpcmUgZmFybS4gJm5ic3A7QmVpbmcgYSByZXNvbHV0ZSBmZWxsb3csIGhlIGRlY2lkZXMgdG8gcmVidWlsZCBpdC4gQWZ0ZXIgcmVidWlsZGluZyBhbGwgTiBmaWVsZHMgKDEgJmx0Oz0gTiAmbHQ7PSA0MDApLCBoZSByZWFsaXplcyBoZSBtdXN0IGFsc28gY29ubmVjdCB0aGUgZmllbGRzIHdpdGggcm9hZHMuICZuYnNwO1doZW4gY29tcGxldGUsIHRoZXJlIG11c3QgYmUgc29tZSB3YXkgdG8gdHJhdmVyc2UgZnJvbSBhbnkgZmllbGQgdG8gYW55IG90aGVyIGZpZWxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZnRlciBzdHVkeWluZyB0aGUgdGVycmFpbiwgRkogaGFzIGNvbmNsdWRlZCB0aGF0IE0gKDEgJmx0Oz0gTSAmbHQ7PSAxMCwwMDApIHR3by13YXkgcm9hZHMgY2FuIHBvc3NpYmx5IGJlIGJ1aWx0LiBTaW5jZSBoZSBpcyBsb3cgb24gbW9uZXksIGhlIHdvdWxkIGxpa2UgdG8gY29tcGxldGUgdGhlIHByb2plY3QgaW4gdGhlIGNoZWFwZXN0IHdheSBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QXMgbHVjayB3b3VsZCBoYXZlIGl0LCB0aGUgY293cyBoYXZlIGZvcm1lZCBhbiBlbmdpbmVlcmluZyBjb25zdWx0aW5nIGZpcm0gdGhhdCBzcGVjaWFsaXplcyBpbiByZWJ1aWxkaW5nIGZhcm0gcm9hZHMgZGVzdHJveWVkIGluIGVhcnRocXVha2VzLiBUaGUgY293cyBhbHNvIGhhdmUgYSBrZWVuIGJ1c2luZXNzIHNlbnNlIGFuZCBoYXZlIG5vIGludGVyZXN0IGluIHRha2luZyBvbiBqb2JzIGZvciB3aGljaCB0aGV5IGRvIG5vdCBtYWtlIGEgaGFuZHNvbWUgcHJvZml0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY293cyBhcmUgY29uY2VybmVkIGFib3V0IHRoZSBwcm9maXQgcG90ZW50aWFsLiAmbmJzcDtUaGV5IGhhdmUgbmVnb3RpYXRlZCBhIGZlZSBGICgxICZsdDs9IEYgJmx0Oz0gMiwwMDAsMDAwLDAwMCkgd2hpY2ggdGhleSBhcmUgcGFpZCB0byByZWJ1aWxkIHRoZSByb2Fkcy4gJm5ic3A7VGhleSBhcmUgZ2l2ZW4gYSB0YWJsZSBvZiBwb3NzaWJsZSByb2FkcywgdGhlIHRpbWUgKGluIGhvdXJzKSB0byBidWlsZCBlYWNoIHJvYWQgKDEgJmx0Oz0gdCAmbHQ7PSAyLDAwMCwwMDAsMDAwKSwgYW5kIHRoZSBjb3N0IHRvIGJ1aWxkIHRoZSByb2FkICgxICZsdDs9IGMgJmx0Oz0gMiwwMDAsMDAwLDAwMCkuICZuYnNwO1RoZSB0YWJsZSBtaWdodCBjb250YWluIG1vcmUgdGhhbiBvbmUgcm9hZCBjb25uZWN0aW5nIHRoZSBzYW1lIHBhaXIgb2YgZmllbGRzLiAmbmJzcDtJdCB3aWxsIGFsd2F5cyBiZSBwb3NzaWJsZSB0byBjb25uZWN0IGFsbCB0aGUgZmllbGRzIGdpdmVuIHRoZSBpbnB1dCBkYXRhIHRob3VnaCBpdCBtaWdodCBub3QgYmUgcHJvZml0YWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBoaWdoZXN0IHByb2ZpdCByYXRlIHRoZSBjb3dzIGNhbiBtYWtlIGluIHJlYnVpbGRpbmcgdGhlIGZhcm0mIzM5O3Mgcm9hZHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVGhyZWUgaW50ZWdlcnMsIE4sIE0sIGFuZCBGJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uLk0rMTogRWFjaCBsaW5lIGNvbnRhaW5zIGZvdXIgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBpLCBqLCBjLCBhbmQgdCByZXNwZWN0aXZlbHkgZGVub3RpbmcgdHdvIGZpZWxkcyB0aGUgcm9hZCBjb25uZWN0cywgdGhlIGNvc3QsIGFuZCB0aGUgdGltZSByZXF1aXJlbWVudHMgdG8gYnVpbGQgdGhlIHJvYWQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSBjb250YWluaW5nIG9uZSBudW1iZXIgLS0gcHJpbnRlZCB0byBmb3VyIGRlY2ltYWwgcGxhY2VzIC0tIHdoaWNoIGlzIHRoZSBtYXhpbXVtIHByb2ZpdCBwZXIgaG91ciB0aGUgY293cyBjYW4gYWNoaWV2ZS4gJm5ic3A7SWYgdGhlIHByb2ZpdCBpcyBub3QgcG9zaXRpdmUsIHByaW50IDAuMDAwMCAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==