#include <cstdio>
#include <vector>
#include <deque>
using namespace std;

const int MAX_N = 300;
const int MAX_W = int(1e4);
const int INF = int(1.05e9); //^@本当にこれで大丈夫？

template<typename numType>
inline bool updateMax(numType& old, const numType& test) {
	if (old < test) {
		old = test;
		return true;
	}
	return false;
}

int N, W;
int stamp[2*MAX_N];
vector<int> times[MAX_N];
bool toDown[2*MAX_N];
int ws[2*MAX_N], vs[2*MAX_N], ms[2*MAX_N];
int opt[2*MAX_N][MAX_W + 1];

class Edge {
public:
	int to;
	int weight, value, amount;

	Edge(){}
	Edge(int to_, int weight_, int value_, int amount_):
		to(to_),  weight(weight_), value(value_), amount(amount_)
	{}
};

class Graph : public vector< vector<Edge> > {
public:
	int numV;

	Graph(){}

	void init(int numV_) {
		numV = numV_;
		init();
	}

	void init() {
		assign(numV, vector<Edge>());
	}

	void addUndirectedEdge(int from, int to, int weight, int value, int amount) {
		operator [](from).push_back(Edge(to, weight, value, amount));
		operator [](to).push_back(Edge(from, weight, value, amount));
	}
};

Graph g;

void init() {
	scanf("%d%d", &N, &W);
	g.init(N);
	for (int i = 0; i < N - 1; ++i) {
		int a, b, w, m, v;
		scanf("%d%d%d%d%d", &a, &b, &w, &m, &v);
		a--;
		b--;
		g.addUndirectedEdge(a, b, w, v, m);
	}
}

void traverse(int v, int parent, int &eu) {
	stamp[eu] = v;
	toDown[eu] = true;
	times[v].push_back(eu);

	for (int i = 0; i < int(g[v].size()); ++i) {
		const Edge &e = g[v][i];
		const int u = e.to;
		if (u != parent) {
			ws[eu] = e.weight;
			vs[eu] = e.value;
			ms[eu] = e.amount;

			traverse(u, v, ++eu);
			stamp[eu] = v;
			toDown[eu] = true;
			times[v].push_back(eu);
		}
	}

	toDown[eu++] = false;
}

int solve() {
	int eu = 0;
	traverse(0, -1, eu);

	for (int i = 1; i < 2*N-1; ++i) {
		fill(opt[i], opt[i] + W + 1, -INF);
	}

	for (int i = 0; i < 2*N-1; ++i) {
		int vert = stamp[i];
		int w = ws[i], m = ms[i], v = vs[i];
		if (toDown[i]) {
			int nextTime = -1;
			for (int j = 0; j + 1 < int(times[vert].size()); ++j) {
				if (i == times[vert][j]) {
					nextTime = times[vert][j+1];
				}
			}
			if (nextTime != -1) {
				for (int j = 0; j <= W; ++j) {
					updateMax(opt[nextTime][j], opt[i][j]);
				}
			}

			if (m%2 == 1) {
				for (int j = 0; j + (m+1)*w <= W; ++j) {
					updateMax(opt[i+1][j+(m+1)*w], opt[i][j] + m*v);
				}
				--m;
			}
			if (m == 0) {
				for (int j = 0; j + 2*w <= W; ++j) {
					updateMax(opt[i+1][j+2*w], opt[i][j]);
				}
			}
			else {
				m -= 2;
				m /= 2;
				if (m > 0) {
					w *= 2; v *= 2;
//					for (int a = 0; a < w; ++a) {
//						deque< pair<int, int> > deq; // (index, value)
//						for (int j = 0; j * w + a <= W; ++j) {
//							int value = opt[i][j * w + a] - j * v;
//							for (; !deq.empty() && deq.back().second <= value; deq.pop_back()) ;
//							deq.push_back( make_pair(j, value) );
//							opt[i][j * w + a] = deq.front().second + j * v;
//							if (deq.front().first == j - m) {
//								deq.pop_front();
//							}
//						}
//					}
					for (int a = 0; a < w; ++a) {
						static pair<int,int> deq[MAX_W + 1];
						int s = 0, t = 0;
						for (int j = 0; j * w + a <= W; ++j) {
							int value = opt[i][j * w + a] - j * v;
							for (; s<t && deq[t-1].second <= value; --t) ;
							deq[t++] = make_pair(j, value);
							opt[i][j * w + a] = deq[s].second + j * v;
							if (deq[s].first == j - m) {
								++s;
							}
						}
					}

					w /= 2; v /= 2;
				}

				for (int j = 0; j + 2*w <= W; ++j) {
					updateMax(opt[i+1][j+2*w], opt[i][j] + 2*v);
				}
			}
		}
		else {
			for (int j = 0; j <= W; ++j) {
				updateMax(opt[i+1][j], opt[i][j]);
			}
		}
	}

	return opt[2*N-1][W&(~1)];
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 24624