Road Repair

A city has a road network in which every road connects two districts. The network is a tree, so between any two districts there is exactly one path. A path here is the sequence of roads you travel along to get from one district to the other.

Many cars use the roads every day, so the roads wear out badly. The city transport department repairs them on a regular schedule. Every road $R$ has a cost $c$ and a benefit $b$. Repairing $R$ costs $c$ and yields the social benefit $b$.

Suppose you repair every road on a path. The cost of the path is the sum of the costs of its roads, and the benefit of the path is the sum of their benefits. Given an upper bound $C$ on cost, find a path whose cost is at most $C$ and whose benefit is as large as possible.

Your program reads from standard input. The input holds $T$ test cases, and the first line gives $T$.

The first line of each test case has $n$, the number of districts in the network ($2 \le n \le 22000$). The districts are numbered $1$ through $n$, and the network always has exactly $n-1$ roads. Each of the next $n-1$ lines has four integers $\alpha$, $\beta$, $c$ and $b$, meaning that the road joining districts $\alpha$ and $\beta$ has cost $c$ and benefit $b$ ($1 \le \alpha, \beta \le n$, $1 \le c, b \le 1000$). The last line gives the cost bound $C$ ($1 \le C \le 2 \times 10^7$).

Your program writes to standard output. Print one line for each test case. The line holds a single integer, the maximum benefit a path can obtain while its cost is at most $C$. If no such path exists, print $0$.