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
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

void chmax(ll &A, ll B) { A = max(A, B); }

struct Edge {
    Edge() {}
    Edge(int to_, int tm_, int lim_, int cost_) : to(to_), tm(tm_), lim(lim_), cost(cost_) {}
    int to, tm, lim, cost;
};
using Graph = vector< vector<Edge> >;

ll N, T, dp[650][10010];
int euler[650], dir[650];
Edge euler_edge[650];
int idx = 0;

void dfs(Graph &G, int cur, int par=-1) {
    euler[idx++] = cur;
    for(auto e : G[cur]) {
        int to = e.to;
        if(to == par) continue;
        euler_edge[idx] = e;
        dir[idx] = 0;
        dfs(G, to, cur);
        euler_edge[idx] = e;
        dir[idx] = 1;
        euler[idx++] = cur;
    }
}

int main() {
    cin >> N >> T;

    Graph G(N);
    for(int i=0; i<N-1; i++) {
        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});
    }
    dfs(G, 0);

    /*
    for(int i=0; i<idx; i++) {
        printf("%d (%d), ", euler[i], euler_edge[i].cost);
    }
    cout << endl;
    */

    vector<int> pre(N, -1);
    fill(dp[0], dp[650], -(1LL << 60));
    // for(int i=0; i<idx; i++) dp[i][0] = 0;
    dp[0][0] = pre[0] = 0;
    for(int i=1; i<idx; i++) {
        int prev_idx = pre[ euler[i] ];

        int tm = euler_edge[i].tm;
        int lim = euler_edge[i].lim;
        int cost = euler_edge[i].cost;

        for(int t=0; t<=T; t++) {
            if(prev_idx >= 0) chmax(dp[i][t], dp[prev_idx][t]);
        }

        if(dir[i] == 1) {
            // 帰り
            for(int t=0; t<=T; t++) {
                chmax(dp[i][t], dp[i-1][t]);
            }
        }
        else {
            // 行き
            if(lim % 2 == 1) {
                ll take_tm = (lim + 1) * tm, take_cost = lim * cost;
                for(int t=take_tm; t<=T; t++) {
                    chmax(dp[i][t], dp[i-1][t - take_tm] + take_cost);
                }
                lim--;
            }

            if(lim == 0) {
                ll take_tm = 2 * tm;
                for(int t=take_tm; t<=T; t++) {
                    chmax(dp[i][t], dp[i-1][t - take_tm]);
                }
            }
            else {
                lim -= 2;
                for(int m=2; lim>0; m*=2) {
                    ll x = min(lim, m); lim -= x;
                    ll take_tm = x * tm, take_cost = x * cost;
                    for(int t=T; t>=take_tm; t--) {
                        chmax(dp[i-1][t], dp[i-1][t - take_tm] + take_cost);
                    }
                }

                ll take_tm = 2 * tm, take_cost = 2 * cost;
                for(int t=take_tm; t<=T; t++) {
                    chmax(dp[i][t], dp[i-1][t - take_tm] + take_cost);
                }
            }
        }

        /*
        for(int t=0; t<=T; t++) {
            if(dp[i][t] < 0) cout << "-INF" << " ";
            else cout << dp[i][t] << " ";
        }
        cout << endl;
        */
        
        pre[ euler[i] ] = i;
    }
    cout << *max_element(dp[idx-1], dp[idx-1] + T + 1) << endl;
    return 0;
}
