가장 긴 최단 경로

방향 그래프와 두 정점 $s$, $t$가 주어진다. 같은 정점 쌍 사이에 간선이 여러 개 있을 수 있지만, 자기 자신으로 돌아오는 간선은 없다.

각 간선 $e$에는 처음 길이 $d_e$와 단가 $c_e$가 정해져 있다. 비용 $x \cdot c_e$를 내면 간선 $e$의 길이를 $d_e$에서 $d_e + x$로 늘릴 수 있다. $x$는 0 이상의 실수이고 정수가 아니어도 된다. 간선의 길이를 줄일 수는 없다.

총비용이 $P$를 넘지 않도록 몇몇 간선을 늘려서, $s$에서 $t$까지 가는 최단 경로의 길이를 최대로 만들어라. $s$에서 $t$로 가는 경로는 적어도 하나 있다.

입력은 테스트 케이스 하나로 이루어지고, 형식은 다음과 같다.

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

첫 줄에 정수 다섯 개 $N$, $M$, $P$, $s$, $t$가 주어진다. $N$ ($2 \le N \le 200$)은 정점 수, $M$ ($1 \le M \le 2000$)은 간선 수, $P$ ($0 \le P \le 10^6$)는 쓸 수 있는 비용의 한도이며, $s$와 $t$ ($1 \le s, t \le N$, $s \ne t$)는 각각 경로의 시작 정점과 끝 정점이다.

이어지는 $M$개의 줄에는 정수 네 개 $v_i$, $u_i$, $d_i$, $c_i$가 주어진다. $v_i$에서 $u_i$로 가는 간선이 있다는 뜻이고 ($1 \le v_i, u_i \le N$, $v_i \ne u_i$), 그 간선의 처음 길이는 $d_i$ ($1 \le d_i \le 10$), 단가는 $c_i$ ($1 \le c_i \le 10$)이다.

비용 $P$ 안에서 간선을 늘려 만들 수 있는 $s$에서 $t$까지 최단 경로 길이의 최댓값을 한 줄에 출력한다.

소수점 아래 여덟째 자리에서 반올림하여 소수점 아래 일곱째 자리까지 출력하고, 모자란 자리는 0으로 채운다. 정확히 중간인 값은 올림한다.