시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 29 15 11 55.000%

문제

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을 출력한다.

예제 입력

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

예제 출력

1.0625

힌트

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