Marathon Course

Interview

Time limit2sMemory limit512 MB

Summary

Choose a simple path from 1 to N minimizing the cost of its roads, where each road costs C*(P-T)^2 when P > T, and find the largest P whose cost fits budget K.

Level: Medium7 of 10
Topics: Shortest path, Graph, Binary search, Heap
Solved: No attempts yet

Problem

A marathon is being held. Runners follow a course fixed in advance, and the course has not been chosen yet. The area of the marathon has $N$ intersections and $M$ two-way roads. A road connects two intersections. Intersections are numbered $1$ to $N$ , and roads are numbered $1$ to $M$ .

A marathon course is written as a list of intersections $(V_1, V_2, \dots, V_k)$ , where $k$ is the number of intersections on the course. The first intersection $V_1$ must always be intersection $1$ , and the last intersection $V_k$ must always be intersection $N$ . No intersection may appear twice, and two consecutive intersections must be connected by a road.

Holding the marathon requires closing every road on the course. Closing a road may or may not cost money. Each road has a closing cost $C$ and a payment threshold $T$ . Let $P$ be the number of people who take part. A road with $P \le T$ is closed at no cost. Closing a road with $P > T$ costs $C \times (P-T)^2$ won. The closing cost of a course is the sum of the costs of the roads on it.

The marathon budget pays at most $K$ won for road closing. The course is chosen so that as many people as possible can take part. Write a program that finds the largest number of people who can take part when the course is chosen well within the budget.

Input

The first line contains the number of intersections $N$ , the number of roads $M$ , and the budget $K$ . ( $2 \le N \le 100{,}000$ , $N-1 \le M \le 100{,}000$ , $1 \le K \le 10^9$ )

Each of the next $M$ lines contains one road, given as four integers $A$ , $B$ , $C$ , $T$ ( $1 \le A < B \le N$ , $1 \le C, T \le 1{,}000$ ). $A$ and $B$ are the two intersections the road connects, and $C$ and $T$ are the values used to compute the cost of closing that road.

At most one road connects any two intersections, and every input has an answer.

Output

Print on the first line the largest number of people who can take part when the course is chosen well within the budget.

Notes

Suppose a course uses two roads whose values are $(C, T) = (5, 1)$ and $(C, T) = (1, 5)$ . With 3 people the closing cost is $5 \times (3-1)^2 + 0 = 20$ won, with 4 people it is $5 \times (4-1)^2 + 0 = 45$ won, and with 6 people it is $5 \times (6-1)^2 + 1 \times (6-5)^2 = 126$ won. With a budget of 25 won, 3 people take part on this course.

Examples4

Example 1
Input
```
3 3 5
1 2 1 1
1 3 1 1
2 3 1 1
```
Expected output
```
3
```
Example 2
Input
```
3 3 3
1 2 1 1
1 3 1 1
2 3 1 1
```
Expected output
```
2
```
Example 3
Input
```
3 2 25
1 2 5 1
2 3 1 5
```
Expected output
```
3
```

Example 4

Input

Expected output