Sanpo

Time Limit : 1 sec, Memory Limit : 65536 KB

さんぽ

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_ib_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

Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  fura2 ,  komiya