마라톤 대회

마라톤 대회가 열린다. 참가자는 미리 정해진 코스를 따라 달려야 하고, 코스는 아직 정해지지 않았다. 대회가 열리는 곳은 $N$개의 교차로와 $M$개의 양방향 도로로 이루어져 있다. 도로는 두 교차로를 잇는다. 교차로에는 $1$번부터 $N$번까지, 도로에는 $1$번부터 $M$번까지 번호가 붙어 있다.

마라톤 코스는 교차로의 나열 $(V_1, V_2, \dots, V_k)$로 나타낸다. $k$는 코스에 들어가는 교차로의 개수이다. 시작 교차로 $V_1$은 항상 $1$번 교차로, 마지막 교차로 $V_k$는 항상 $N$번 교차로여야 한다. 같은 교차로가 두 번 이상 나오면 안 되고, 연속한 두 교차로는 도로로 이어져 있어야 한다.

대회를 열려면 코스에 들어가는 도로를 통제해야 한다. 도로를 통제하는 데 비용을 지불할 수도 있고 지불하지 않을 수도 있다. 각 도로에는 통제 비용 $C$와 지불 인원 상한선 $T$가 있다. 마라톤에 참가하는 사람의 수를 $P$라고 하면, $P \le T$인 도로는 비용을 지불하지 않고 통제한다. $P > T$인 도로를 통제하는 비용은 $C \times (P-T)^2$원이다. 코스의 통제 비용은 코스에 들어가는 도로의 비용을 모두 더한 값이다.

대회 예산 중에서 도로 통제에 지불할 수 있는 금액은 최대 $K$원이다. 코스는 참가할 수 있는 사람이 가장 많아지도록 정하려고 한다. 예산 안에서 코스를 적절히 정했을 때 참가할 수 있는 사람 수의 최댓값을 구하는 프로그램을 작성하시오.

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

둘째 줄부터 $M$개의 줄에 도로의 정보가 한 줄에 하나씩 주어진다. 도로의 정보는 네 정수 $A$, $B$, $C$, $T$ ($1 \le A < B \le N$, $1 \le C, T \le 1{,}000$)로 이루어진다. $A$와 $B$는 도로가 잇는 두 교차로의 번호이고, $C$와 $T$는 그 도로를 통제하는 비용을 계산하는 데 쓰는 값이다.

임의의 두 교차로를 잇는 도로는 많아야 한 개이고, 항상 답을 구할 수 있는 경우만 입력으로 주어진다.

예산 안에서 코스를 적절히 정했을 때 참가할 수 있는 사람 수의 최댓값을 첫째 줄에 출력한다.

코스에 도로 두 개가 들어가고 두 도로의 값이 각각 $(C, T) = (5, 1)$, $(C, T) = (1, 5)$라고 하자. 참가자가 3명이면 통제 비용은 $5 \times (3-1)^2 + 0 = 20$원이고, 4명이면 $5 \times (4-1)^2 + 0 = 45$원이며, 6명이면 $5 \times (6-1)^2 + 1 \times (6-5)^2 = 126$원이다. 예산이 25원이면 이 코스로는 3명까지 참가한다.