시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB294997341.954%

문제

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가 된다.

W3sicHJvYmxlbV9pZCI6IjIxMjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWM5YzQiLCJkZXNjcmlwdGlvbiI6IjxwPk4oNCAmbGU7IE4gJmxlOyA0MDApXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YWNmYyBNKDEgJmxlOyBNICZsZTsgMTAsMDAwKVx1YWMxY1x1Yzc1OCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHVhYzA0XHVjMTIwXHViNGU0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YzljMFx1YzljNFx1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWMxMWMgXHViYWE4XHViNGUwIFx1YWMwNFx1YzEyMFx1YjRlNFx1Yzc3NCBcdWIwNGFcdWM1YjRcdWM4MzggXHViYzg0XHViODM4XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNzc0IFx1YWMwNFx1YzEyMFx1YjRlNCBcdWM5MTEgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWJjZjVcdWM2ZDBcdWQ1NThcdWM1ZWMgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjZjVcdWM2ZDAgXHViZTQ0XHVjNmE5XHVjNzNjXHViODVjXHViMjk0IEYoMSAmbGU7IEYgJmxlOyAyLDAwMCwwMDAsMDAwKVx1YzZkMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVhYzA0XHVjMTIwXHViNGU0XHVjNWQwXHViMjk0IFx1YWRmOCBcdWFjMDRcdWMxMjBcdWM3NDQgXHViY2Y1XHVjNmQwXHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDQgdCgxICZsZTsgdCAmbGU7IDIsMDAwLDAwMCwwMDApXHVjNjQwIFx1YWRmOCBcdWFjMDRcdWMxMjBcdWM3NDQgXHViY2Y1XHVjNmQwXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJlNDRcdWM2YTkgYygxICZsZTsgYyAmbGU7IDIsMDAwLDAwMCwwMDApXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3YyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWFjMTlcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzc4XHViMzcwIFx1YmNmNVx1YzZkMCBcdWJlNDRcdWM2YTlcdWM3NzRcdWIwOTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJjZjVcdWM2ZDAgXHViZTQ0XHVjNmE5XHVjNzc0IEZcdWI5N2MgXHViMTE4XHVhYzhjIFx1YjQxOFx1YjM1NFx1Yjc3Y1x1YjNjNCwgXHViY2Y1XHVjNmQwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwNFx1YzEyMFx1YjRlNFx1Yzc0NCBcdWJjZjVcdWM2ZDBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWMyZGNcdWFjMDRcdWIyZjkgXHVjNWJiXHVhYzhjIFx1YjQxOFx1YjI5NCBcdWM3NzRcdWI0ZGRcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YzczY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBOLCBNLCBGXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IGksIGosIGMsIHRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpLCBqXHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIGNcdWIyOTQgXHViZTQ0XHVjNmE5LCB0XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1YWMwNFx1YjJmOSBcdWM1YmJcdWFjOGMgXHViNDE4XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWM3NzRcdWI0ZGRcdWM3NDQgXHVjMThjXHVjMjJiXHVjODEwIFx1YzU0NFx1Yjc5OCBcdWIxMzdcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Yzc3NFx1YjRkZFx1Yzc3NCBcdWM1OTFcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmM4XHViYTc0IDAuMDAwMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjIsIDMsIDQsIDVcdWJjODggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjZDVjXHVjODAxXHVkNTc0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGNcdWM3NTggXHVjZDFkIFx1YmU0NFx1YzZhOVx1Yzc0MCA4M1x1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMTZcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc0XHViNGRkXHVjNzQwIDEwMC04Mz0xN1x1YzZkMFx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMyZGNcdWFjMDRcdWIyZjkgXHVjNWJiXHViMjk0IFx1Yzc3NFx1YjRkZFx1Yzc0MCAxN1wvMTY9MS4wNjI1XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIxMjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFYXJ0aHF1YWtlIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBlYXJ0aHF1YWtlIGhhcyBkZXN0cm95ZWQgRmFybWVyIEpvaG4mIzM5O3MgZW50aXJlIGZhcm0uICZuYnNwO0JlaW5nIGEgcmVzb2x1dGUgZmVsbG93LCBoZSBkZWNpZGVzIHRvIHJlYnVpbGQgaXQuIEFmdGVyIHJlYnVpbGRpbmcgYWxsIE4gZmllbGRzICgxICZsdDs9IE4gJmx0Oz0gNDAwKSwgaGUgcmVhbGl6ZXMgaGUgbXVzdCBhbHNvIGNvbm5lY3QgdGhlIGZpZWxkcyB3aXRoIHJvYWRzLiAmbmJzcDtXaGVuIGNvbXBsZXRlLCB0aGVyZSBtdXN0IGJlIHNvbWUgd2F5IHRvIHRyYXZlcnNlIGZyb20gYW55IGZpZWxkIHRvIGFueSBvdGhlciBmaWVsZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgc3R1ZHlpbmcgdGhlIHRlcnJhaW4sIEZKIGhhcyBjb25jbHVkZWQgdGhhdCBNICgxICZsdDs9IE0gJmx0Oz0gMTAsMDAwKSB0d28td2F5IHJvYWRzIGNhbiBwb3NzaWJseSBiZSBidWlsdC4gU2luY2UgaGUgaXMgbG93IG9uIG1vbmV5LCBoZSB3b3VsZCBsaWtlIHRvIGNvbXBsZXRlIHRoZSBwcm9qZWN0IGluIHRoZSBjaGVhcGVzdCB3YXkgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzIGx1Y2sgd291bGQgaGF2ZSBpdCwgdGhlIGNvd3MgaGF2ZSBmb3JtZWQgYW4gZW5naW5lZXJpbmcgY29uc3VsdGluZyBmaXJtIHRoYXQgc3BlY2lhbGl6ZXMgaW4gcmVidWlsZGluZyBmYXJtIHJvYWRzIGRlc3Ryb3llZCBpbiBlYXJ0aHF1YWtlcy4gVGhlIGNvd3MgYWxzbyBoYXZlIGEga2VlbiBidXNpbmVzcyBzZW5zZSBhbmQgaGF2ZSBubyBpbnRlcmVzdCBpbiB0YWtpbmcgb24gam9icyBmb3Igd2hpY2ggdGhleSBkbyBub3QgbWFrZSBhIGhhbmRzb21lIHByb2ZpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNvd3MgYXJlIGNvbmNlcm5lZCBhYm91dCB0aGUgcHJvZml0IHBvdGVudGlhbC4gJm5ic3A7VGhleSBoYXZlIG5lZ290aWF0ZWQgYSBmZWUgRiAoMSAmbHQ7PSBGICZsdDs9IDIsMDAwLDAwMCwwMDApIHdoaWNoIHRoZXkgYXJlIHBhaWQgdG8gcmVidWlsZCB0aGUgcm9hZHMuICZuYnNwO1RoZXkgYXJlIGdpdmVuIGEgdGFibGUgb2YgcG9zc2libGUgcm9hZHMsIHRoZSB0aW1lIChpbiBob3VycykgdG8gYnVpbGQgZWFjaCByb2FkICgxICZsdDs9IHQgJmx0Oz0gMiwwMDAsMDAwLDAwMCksIGFuZCB0aGUgY29zdCB0byBidWlsZCB0aGUgcm9hZCAoMSAmbHQ7PSBjICZsdDs9IDIsMDAwLDAwMCwwMDApLiAmbmJzcDtUaGUgdGFibGUgbWlnaHQgY29udGFpbiBtb3JlIHRoYW4gb25lIHJvYWQgY29ubmVjdGluZyB0aGUgc2FtZSBwYWlyIG9mIGZpZWxkcy4gJm5ic3A7SXQgd2lsbCBhbHdheXMgYmUgcG9zc2libGUgdG8gY29ubmVjdCBhbGwgdGhlIGZpZWxkcyBnaXZlbiB0aGUgaW5wdXQgZGF0YSB0aG91Z2ggaXQgbWlnaHQgbm90IGJlIHByb2ZpdGFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgaGlnaGVzdCBwcm9maXQgcmF0ZSB0aGUgY293cyBjYW4gbWFrZSBpbiByZWJ1aWxkaW5nIHRoZSBmYXJtJiMzOTtzIHJvYWRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFRocmVlIGludGVnZXJzLCBOLCBNLCBhbmQgRiZuYnNwOzxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLi5NKzE6IEVhY2ggbGluZSBjb250YWlucyBmb3VyIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogaSwgaiwgYywgYW5kIHQgcmVzcGVjdGl2ZWx5IGRlbm90aW5nIHR3byBmaWVsZHMgdGhlIHJvYWQgY29ubmVjdHMsIHRoZSBjb3N0LCBhbmQgdGhlIHRpbWUgcmVxdWlyZW1lbnRzIHRvIGJ1aWxkIHRoZSByb2FkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBvbmUgbnVtYmVyIC0tIHByaW50ZWQgdG8gZm91ciBkZWNpbWFsIHBsYWNlcyAtLSB3aGljaCBpcyB0aGUgbWF4aW11bSBwcm9maXQgcGVyIGhvdXIgdGhlIGNvd3MgY2FuIGFjaGlldmUuICZuYnNwO0lmIHRoZSBwcm9maXQgaXMgbm90IHBvc2l0aXZlLCBwcmludCAwLjAwMDAgLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d