시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 512 MB76161318.571%

문제

You are given a directed graph and two nodes s and t. The given graph may contain multiple edges between the same node pair but not self loops. Each edge e has its initial length de and the cost ce. You can extend an edge by paying a cost. Formally, it costs x⋅ce to change the length of an edge e from de to de+x. (Note that x can be a non-integer.) Edges cannot be shortened.

Your task is to maximize the length of the shortest path from node s to node tt by lengthening some edges within cost P. You can assume that there is at least one path from s to t.

입력

The input consists of a single test case formatted as follows.

N M P s t
v1 u1 d1 c1
...
vM uM dM cM

The first line contains five integers N, M, P, s, and t: N (2 ≤ N ≤ 200) and M (1 ≤ M ≤ 2,000) are the number of the nodes and the edges of the given graph respectively, P (0 ≤ P ≤ 106) is the cost limit that you can pay, and s and t (1 ≤ s,t ≤ N, s ≠ t) are the start and the end node of objective path respectively. Each of the following M lines contains four integers vi, ui, di, and ci, which mean there is an edge from vi to ui (1 ≤ vi,ui ≤ N, vi ≠ ui) with the initial length di (1 ≤ di ≤ 10) and the cost ci (1 ≤ c≤ 10).

출력

Output the maximum length of the shortest path from node s to node t by lengthening some edges within cost P. The output can contain an absolute or a relative error no more than 10−6.

예제 입력 1

3 2 3 1 3
1 2 2 1
2 3 1 2

예제 출력 1

6.0000000

예제 입력 2

3 3 2 1 3
1 2 1 1 
2 3 1 1
1 3 1 1

예제 출력 2

2.5000000

예제 입력 3

3 4 5 1 3
1 2 1 2
2 3 1 1
1 3 3 2
1 3 4 1

예제 출력 3

4.2500000