#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<(b)?(a=b,1):0)
#define chmin(a,b) (a>(b)?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

struct Edge {
  int dst,t,m,v;
  Edge(int dst, int t, int m, int v) :
    dst(dst),t(t),m(m),v(v) {}
};

int n, T;
vector<Edge> g[300];

vector<int> tour;
vector<Edge> tourEdge;

void dfs(int now, int pre) {
  tour.push_back(now);
  FOR(it, g[now]) {
    if (it->dst == pre) continue;
    
    tourEdge.push_back(*it);
    dfs(it->dst, now);
    tourEdge.push_back(*it);
    tour.push_back(now);
  }
}

ll dp[600][10001];
int prev[300];

int deq[10001];
ll deqv[10001];

const ll NEGINF = -1e15;

int main() {
  while(cin >> n >> T) {
    REP(i,n) g[i].clear();
    REP(i,n-1) {
      int a, b, t,m,v;
      cin>>a>>b>>t>>m>>v;
      a--;b--;
      g[a].push_back(Edge(b,t,m,v));
      g[b].push_back(Edge(a,t,m,v));
    }

    tour.clear();
    tourEdge.clear();
    dfs(0,-1);

    assert(tour.size() == n*2-1);
    
    memset(dp,-1,sizeof(dp));
    memset(prev,-1,sizeof(prev));
    
    dp[0][0] = 0;
    
    REP(i,tour.size()-1) {
//      cout << i << ": " << tour[i+1]+1 << " " << tourEdge[i].dst+1 << " "<< tourEdge[i].m << endl;
//      cout << prev[tour[i+1]] << endl;
      if (prev[tour[i+1]] != -1) {
        REP(j,T+1) {
          chmax(dp[i+1][j], dp[prev[tour[i+1]]][j]);
        }
      }
      prev[tour[i]] = i;
      if (tour[i+1] == tourEdge[i].dst) {
        // 行き
        if (tourEdge[i].m >= 2) {
          int w = tourEdge[i].t * 2;
          REP(a,w) {
            int s = 0, t = 0;
            for (int j=0; j*w+a <= T; ++j) {
              if (j && deqv[s] != NEGINF) {
                assert(deq[s] != j);
                chmax(dp[i+1][j*w+a], deqv[s] + j*tourEdge[i].v*2);
              }
              
              if (deq[s] == j-tourEdge[i].m/2) s++;
              ll val = dp[i][j*w+a] - j*tourEdge[i].v*2;
              if (dp[i][j*w+a] == -1) val = NEGINF;
              while(s<t && deqv[t-1] <= val) t--;
              deq[t] = j;
              deqv[t++] = val;

            }
          }
        }
        if (tourEdge[i].m&1) {
          REP(j,T+1) {
            int t = j+(tourEdge[i].m+1)*tourEdge[i].t;
            if (t > T) break;
            if (dp[i][j] != -1) {
              // cout << ":"<<tourEdge[i].m << endl;
              chmax(dp[i+1][t], dp[i][j] + tourEdge[i].m*tourEdge[i].v);
            }
          }
        } else if (tourEdge[i].m == 0) {
          REP(j,T+1) {
            int t = j+2*tourEdge[i].t;
            if (t > T) break;
            chmax(dp[i+1][t], dp[i][j]);
          }
        }
      } else {
        REP(j,T+1) {
          chmax(dp[i+1][j], dp[i][j]);
        }
      }
      // REP(j,20) cout << (dp[i+1][j]<0?-1:dp[i+1][j]) << " "; cout << endl;
      
    }
    ll ans = 0;
    REP(t,T+1) {
      if (chmax(ans, dp[tour.size()-1][t])) {
        // cout << t << endl;
      }
    }
    cout << ans << endl;

  }
}

Measured memory_bytes: 48224