import sys
import threading
import bisect

def main():
    import sys

    sys.setrecursionlimit(1 << 25)
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M = map(int, sys.stdin.readline().split())
        children = [[] for _ in range(N + 1)]
        C = [0] * (N + 1)
        L = [0] * (N + 1)
        for i in range(1, N + 1):
            line = sys.stdin.readline()
            if not line.strip():
                line = sys.stdin.readline()
            tokens = line.strip().split()
            if len(tokens) !=3:
                RM, cost, leadership = 0, 0, 0
            else:
                RM, cost, leadership = map(int, tokens)
            if i ==1:
                if RM ==1:
                    parent =0
                else:
                    parent = RM
            else:
                parent = RM
            children[parent].append(i)
            C[i] = cost
            L[i] = leadership
        max_happiness = 0

        def dfs(node):
            nonlocal max_happiness
            current_costs = [C[node]]
            current_costs.sort()
            for child in children[node]:
                child_costs = dfs(child)
                if len(child_costs) > len(current_costs):
                    current_costs, child_costs = child_costs, current_costs
                merged = []
                i = j =0
                while i < len(current_costs) and j < len(child_costs):
                    if current_costs[i] < child_costs[j]:
                        merged.append(current_costs[i])
                        i +=1
                    else:
                        merged.append(child_costs[j])
                        j +=1
                while i < len(current_costs):
                    merged.append(current_costs[i])
                    i +=1
                while j < len(child_costs):
                    merged.append(child_costs[j])
                    j +=1
                current_costs = merged
            prefix_sums = [0]
            for cost in current_costs:
                prefix_sums.append(prefix_sums[-1] + cost)
            k = bisect.bisect_right(prefix_sums, M) -1
            happiness = L[node] * k
            if happiness > max_happiness:
                max_happiness = happiness
            return current_costs

        dfs(0)
        print(max_happiness)

threading.Thread(target=main).start()

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int solve(string s) {
    if (s.empty() || s[0] == '0') {
        return 0;  
    }
    
    int n = s.size();
    vector<int> dp(n + 1, 0); 
    dp[0] = 1;  
    dp[1] = 1; 
    
    for (int i = 2; i <= n; ++i) {
        if (s[i - 1] >= '1' && s[i - 1] <= '9') {
            dp[i] += dp[i - 1];
        }
        int t = stoi(s.substr(i - 2, 2));
        if (t >= 10 && t <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[n]; 
}

int main() {
    string s;
    cin >> s;
    int result = solve(s);
    cout << result << endl;

    return 0;
}

import re
a = ["Inc.", "Corp.", "LLC", "L.L.C.", "LLC."]
b = ["the", "an", "a", "and"]
def normalize_name(c):
    c = c.lower()
    for d in a:
        if c.endswith(d.lower()):
            c = c[:-len(d)].strip()
    c = re.sub(r'[&,]', ' ', c) 
    c = re.sub(r'\s+', ' ', c)  
    d = c.split()
    if d[0] in b:
        d = d[1:]
    c = ' '.join(d)
    return c.strip()
def check_availability(d):
    e = set()  
    for f in d:
        g, c = f.split('|')
        h = normalize_name(c)
        if not h:
            print(f"{g}|Name Not Available")
        elif h in e:
            print(f"{g}|Name Not Available")
        else:
            e.add(h)
            print(f"{g}|Name Available")