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 c_e. You can extend an edge by paying a cost. Formally, it costs x⋅c_e to change the length of an edge e from d_e to d_e+x. (Note that x can be a non-integer.) Edges cannot be shortened.</p>

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.</p>

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 ≤ 10⁶) 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 v_i, u_i, d_i, and c_i, which mean there is an edge from v_i to u_i (1 ≤ v_i,u_i ≤ N, v_i ≠ u_i) with the initial length d_i (1 ≤ d_i ≤ 10) and the cost c_i (1 ≤ c_i ≤ 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⁻⁶.

예제 입력 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