도로 보수

한 도시에 도로망이 있다. 도로는 저마다 두 구역을 잇는다. 이 도로망은 트리 구조여서 임의의 두 구역 사이에는 정확히 하나의 경로가 있다. 여기서 경로란 한 구역에서 다른 구역까지 이동하며 지나는 도로의 나열이다.

날마다 수많은 차량이 지나다니는 탓에 도로는 심하게 손상된다. 시 교통국은 도로를 정기적으로 보수한다. 각 도로 $R$에는 비용 $c$와 이득 $b$가 정해져 있다. 비용 $c$를 들여 도로 $R$을 보수하면 사회적 이득 $b$를 얻는다.

한 경로에 속한 도로를 모두 보수한다고 하자. 이때 경로의 비용은 속한 도로의 비용 합이고, 경로의 이득은 속한 도로의 이득 합이다. 비용 상한 $C$가 주어질 때, 비용이 $C$ 이하이면서 이득이 가장 큰 경로를 찾아라.

프로그램은 표준 입력에서 읽는다. 입력은 $T$개의 테스트 케이스로 이루어지고, 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 도로망의 구역 수 $n$이 주어진다 ($2 \le n \le 22000$). 구역에는 $1$부터 $n$까지 번호가 매겨져 있고, 도로는 언제나 정확히 $n-1$개다. 이어지는 $n-1$개의 줄에는 각각 네 정수 $\alpha$, $\beta$, $c$, $b$가 주어진다. 이는 구역 $\alpha$와 $\beta$를 잇는 도로의 비용이 $c$이고 이득이 $b$라는 뜻이다 ($1 \le \alpha, \beta \le n$, $1 \le c, b \le 1000$). 마지막 줄에는 비용 상한 $C$가 주어진다 ($1 \le C \le 2 \times 10^7$).

프로그램은 표준 출력에 쓴다. 테스트 케이스마다 한 줄씩 출력한다. 각 줄에는 비용이 $C$ 이하인 경로가 얻을 수 있는 최대 이득을 정수 하나로 출력한다. 그런 경로가 없으면 $0$을 출력한다.