퍼레이드

미르코는 작년 군사 퍼레이드에 푹 빠졌고, 그중에서도 탱크가 가장 인상 깊었다. 그래서 내년 퍼레이드 준비에 직접 참여하기로 했다. 퍼레이드는 도시를 가로지르는 행진으로 진행된다. 탱크를 포함한 모든 부대가 미리 정한 도로를 따라 차례로 이동하며, 한 번 지나간 곳으로는 되돌아가지 않는다.

미르코의 개인적인 목표는 퍼레이드에 탱크를 최대한 많이 참가시키는 것이다. 이 수를 $T$라고 하자. 문제는 탱크가 무거워서 지나가는 도로를 망가뜨린다는 점이다. 모든 도로는 양방향이고 두 교차로를 잇는다. 도로 $i$는 수리가 필요해지기 전까지 탱크 $T_i$대가 지나갈 수 있다. 그보다 많은 탱크가 지나가면 도로 $i$의 수리 비용은 탱크 수에 따라 제곱으로 늘어나며, $C_i \cdot (T - T_i)^2$천 쿠나이다. 여기서 $C_i$는 도로 $i$의 수리 비용 계수이다. $T \le T_i$이면 도로 $i$의 수리 비용은 0이다.

다행히 도로 보수에 쓰는 연간 예산 $K$천 쿠나가 있고, 이 예산은 탱크가 지나갈 도로를 보수하는 데에만 골라 쓸 수 있다. 미르코는 도로 수리 비용의 합이 예산을 넘지 않게 하면서 탱크 수를 최대로 만드는 퍼레이드 경로를 짜야 한다. 추가로 퍼레이드는 교차로 1에서 출발해 교차로 $N$에서 끝나야 하며, 그런 경로가 적어도 하나 있음이 보장된다.

첫째 줄에 교차로의 수 $N$, 도로의 수 $M$, 천 쿠나 단위의 예산 $K$가 주어진다. ($2 \le N \le 100\,000$, $N-1 \le M \le 100\,000$, $1 \le K \le 10^9$)

다음 $M$개 줄에는 각각 네 정수 $A_i$, $B_i$, $C_i$, $T_i$가 주어진다. ($1 \le A_i < B_i \le N$, $1 \le C_i, T_i \le 1000$) 차례로 도로 $i$가 잇는 두 교차로, 수리 비용 계수, 수리 없이 지나갈 수 있는 탱크 수를 뜻한다. 두 교차로를 잇는 도로는 많아야 하나이다.

수리 비용이 예산 $K$를 넘지 않도록 할 때 퍼레이드에 참가할 수 있는 탱크 수의 최댓값을 출력한다.