#D3286. Sanpo
Sanpo
Sanpo
Sanpo
Problem Statement
The cats love walking. There are new discoveries as you walk down the road.
The town where Sora lives consists of N squares and N-1 roads. The road just connects the two squares and does not branch or intersect.
For the road, the time t to walk, the upper limit m of the number of discoveries that can be obtained, and the value v per discovery are specified. When walking along the road from one end to the other, one discovery of value v can be obtained in the mth pass, but no discovery can be obtained after the m + 1th pass.
It seems that they are going for a walk in the town today. The walk in the sky starts at Square 1, takes several roads (maybe 0), and finally returns to Square 1. Also, when the sun goes down, I feel lonely, so I want to set the walking time to T or less.
Your friend, your job, is to find the maximum sum of the values of discoveries you can get on a walk route with a walk time of T or less.
Constraints
- 1 ≤ N ≤ 300
- 1 ≤ T ≤ 10 ^ 4
- 1 ≤ a_i, b_i ≤ N
- 1 ≤ t_i ≤ 10 ^ 4
- 0 ≤ m_i ≤ 10 ^ 4
- 1 ≤ v_i ≤ 10 ^ 5
- You can go back and forth between the two squares.
Input
Input follows the following format. All given numbers are integers.
N T a_1 b_1 t_1 m_1 v_1 .. .. a_ {N-1} b_ {N-1} t_ {N-1} m_ {N-1} v_ {N-1}
The i + 1 line of the input shows the path of the passage time t_i, the upper limit of the number of discoveries obtained, m_i, and the value v_i per discovery, which connects the squares a_i and b_i.
Output
Output the maximum value of the total value of the findings obtained on one line.
Examples
Input
4 5 1 2 1 4 7 2 3 1 2 77 2 4 1 2 777
Output
1568
Input
2 10000 1 2 1 10 1
Output
10
Input
5 15 1 2 3 2 1 2 3 3 2 1 1 4 8 2 777 1 5 1 3 10
Output
32
inputFormat
Input
Input follows the following format. All given numbers are integers.
N T a_1 b_1 t_1 m_1 v_1 .. .. a_ {N-1} b_ {N-1} t_ {N-1} m_ {N-1} v_ {N-1}
The i + 1 line of the input shows the path of the passage time t_i, the upper limit of the number of discoveries obtained, m_i, and the value v_i per discovery, which connects the squares a_i and b_i.
outputFormat
Output
Output the maximum value of the total value of the findings obtained on one line.
Examples
Input
4 5 1 2 1 4 7 2 3 1 2 77 2 4 1 2 777
Output
1568
Input
2 10000 1 2 1 10 1
Output
10
Input
5 15 1 2 3 2 1 2 3 3 2 1 1 4 8 2 777 1 5 1 3 10
Output
32
样例
2 10000
1 2 1 10 110