시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 49 24 19 55.882%

문제

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+MiwgMywgNCwgNVx1YmM4OCBcdWFjMDRcdWMxMjBcdWM3NDQgXHViY2Y1XHVjNmQwXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWNkNWNcdWM4MDFcdWQ1NzRcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0Y1x1Yzc1OCBcdWNkMWQgXHViZTQ0XHVjNmE5XHVjNzQwIDgzXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAxNlx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3NzRcdWI0ZGRcdWM3NDAgMTAwLTgzPTE3XHVjNmQwXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHViNTMwXHViNzdjXHVjMTFjIFx1YzJkY1x1YWMwNFx1YjJmOSBcdWM1YmJcdWIyOTQgXHVjNzc0XHViNGRkXHVjNzQwIDE3XC8xNj0xLjA2MjVcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+Iiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMTI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWFydGhxdWFrZSIsImRlc2NyaXB0aW9uIjoiPHA+QW4gZWFydGhxdWFrZSBoYXMgZGVzdHJveWVkIEZhcm1lciBKb2huJiMzOTtzIGVudGlyZSBmYXJtLiAmbmJzcDtCZWluZyBhIHJlc29sdXRlIGZlbGxvdywgaGUgZGVjaWRlcyB0byByZWJ1aWxkIGl0LiBBZnRlciByZWJ1aWxkaW5nIGFsbCBOIGZpZWxkcyAoMSAmbHQ7PSBOICZsdDs9IDQwMCksIGhlIHJlYWxpemVzIGhlIG11c3QgYWxzbyBjb25uZWN0IHRoZSBmaWVsZHMgd2l0aCByb2Fkcy4gJm5ic3A7V2hlbiBjb21wbGV0ZSwgdGhlcmUgbXVzdCBiZSBzb21lIHdheSB0byB0cmF2ZXJzZSBmcm9tIGFueSBmaWVsZCB0byBhbnkgb3RoZXIgZmllbGQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIHN0dWR5aW5nIHRoZSB0ZXJyYWluLCBGSiBoYXMgY29uY2x1ZGVkIHRoYXQgTSAoMSAmbHQ7PSBNICZsdDs9IDEwLDAwMCkgdHdvLXdheSByb2FkcyBjYW4gcG9zc2libHkgYmUgYnVpbHQuIFNpbmNlIGhlIGlzIGxvdyBvbiBtb25leSwgaGUgd291bGQgbGlrZSB0byBjb21wbGV0ZSB0aGUgcHJvamVjdCBpbiB0aGUgY2hlYXBlc3Qgd2F5IHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBsdWNrIHdvdWxkIGhhdmUgaXQsIHRoZSBjb3dzIGhhdmUgZm9ybWVkIGFuIGVuZ2luZWVyaW5nIGNvbnN1bHRpbmcgZmlybSB0aGF0IHNwZWNpYWxpemVzIGluIHJlYnVpbGRpbmcgZmFybSByb2FkcyBkZXN0cm95ZWQgaW4gZWFydGhxdWFrZXMuIFRoZSBjb3dzIGFsc28gaGF2ZSBhIGtlZW4gYnVzaW5lc3Mgc2Vuc2UgYW5kIGhhdmUgbm8gaW50ZXJlc3QgaW4gdGFraW5nIG9uIGpvYnMgZm9yIHdoaWNoIHRoZXkgZG8gbm90IG1ha2UgYSBoYW5kc29tZSBwcm9maXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzIGFyZSBjb25jZXJuZWQgYWJvdXQgdGhlIHByb2ZpdCBwb3RlbnRpYWwuICZuYnNwO1RoZXkgaGF2ZSBuZWdvdGlhdGVkIGEgZmVlIEYgKDEgJmx0Oz0gRiAmbHQ7PSAyLDAwMCwwMDAsMDAwKSB3aGljaCB0aGV5IGFyZSBwYWlkIHRvIHJlYnVpbGQgdGhlIHJvYWRzLiAmbmJzcDtUaGV5IGFyZSBnaXZlbiBhIHRhYmxlIG9mIHBvc3NpYmxlIHJvYWRzLCB0aGUgdGltZSAoaW4gaG91cnMpIHRvIGJ1aWxkIGVhY2ggcm9hZCAoMSAmbHQ7PSB0ICZsdDs9IDIsMDAwLDAwMCwwMDApLCBhbmQgdGhlIGNvc3QgdG8gYnVpbGQgdGhlIHJvYWQgKDEgJmx0Oz0gYyAmbHQ7PSAyLDAwMCwwMDAsMDAwKS4gJm5ic3A7VGhlIHRhYmxlIG1pZ2h0IGNvbnRhaW4gbW9yZSB0aGFuIG9uZSByb2FkIGNvbm5lY3RpbmcgdGhlIHNhbWUgcGFpciBvZiBmaWVsZHMuICZuYnNwO0l0IHdpbGwgYWx3YXlzIGJlIHBvc3NpYmxlIHRvIGNvbm5lY3QgYWxsIHRoZSBmaWVsZHMgZ2l2ZW4gdGhlIGlucHV0IGRhdGEgdGhvdWdoIGl0IG1pZ2h0IG5vdCBiZSBwcm9maXRhYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EZXRlcm1pbmUgdGhlIGhpZ2hlc3QgcHJvZml0IHJhdGUgdGhlIGNvd3MgY2FuIG1ha2UgaW4gcmVidWlsZGluZyB0aGUgZmFybSYjMzk7cyByb2Fkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUaHJlZSBpbnRlZ2VycywgTiwgTSwgYW5kIEYmbmJzcDs8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi4uTSsxOiBFYWNoIGxpbmUgY29udGFpbnMgZm91ciBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IGksIGosIGMsIGFuZCB0IHJlc3BlY3RpdmVseSBkZW5vdGluZyB0d28gZmllbGRzIHRoZSByb2FkIGNvbm5lY3RzLCB0aGUgY29zdCwgYW5kIHRoZSB0aW1lIHJlcXVpcmVtZW50cyB0byBidWlsZCB0aGUgcm9hZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgb25lIG51bWJlciAtLSBwcmludGVkIHRvIGZvdXIgZGVjaW1hbCBwbGFjZXMgLS0gd2hpY2ggaXMgdGhlIG1heGltdW0gcHJvZml0IHBlciBob3VyIHRoZSBjb3dzIGNhbiBhY2hpZXZlLiAmbmJzcDtJZiB0aGUgcHJvZml0IGlzIG5vdCBwb3NpdGl2ZSwgcHJpbnQgMC4wMDAwIC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d