さんぽ

Problem Statement

ねこのそらは散歩が大好きだ．道を歩くと新しい発見がある．

そらの住む町は N 個の広場と N-1 本の道からなる．
道はちょうど二つの広場をつないでおり，枝分かれしたり道どうしが交わったりしない．

道には，歩くのにかかる時間 t，得られる発見の個数の上限 m，および，発見一つあたりの価値 v が指定されている．
道を一方の端からもう一方の端まで歩いたとき，m 回目までの通行では価値 v の発見が一つ得られるが，m+1 回目以降は発見が得られない．

今日もそらは，町内の散歩に出かけるようだ．
そらの散歩は広場 1 から始まり，いくつかの道 ( 0 本かもしれない ) を通って，最後に広場 1 に戻ってくる，というルートをとる．
また，日が暮れると寂しい気持ちになるので，そらは散歩時間を T 以下にしたいと思っている．

そらの友人であるあなたの仕事は，散歩時間が T 以下である散歩ルートにおいて，得られる発見の価値の総和の最大値を求めることである．

Input

入力は以下の形式に従う．与えられる数は全て整数である．

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}

入力の i+1 行目は，広場 a_i と b_i をつなぐ，通行時間 t_i，得られる発見の個数の上限 m_i，発見一つあたりの価値 v_i の道を表している．

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
• どの二つの広場も道を通って行き来できる．

Output

得られる発見の価値の総和の最大値を 1 行に出力せよ．

Sample Input 1

4 5
1 2 1 4 7
2 3 1 2 77
2 4 1 2 777

Output for the Sample Input 1

1568

1→2→4→2→1 と移動することで，合計で価値 7+777+777+7=1568 の発見が得られる．

Sample Input 2

2 10000
1 2 1 10 1

Output for the Sample Input 2

10

Sample Input 3

5 15
1 2 3 2 1
2 3 3 2 1
1 4 8 2 777
1 5 1 3 10

Output for the Sample Input 3

32