In an outsourcing company, Employees are outsourced to clients and paid for their work. In this company, every employee (except for the CEO) has a RM (Reporting Manager). Any employee takes task assignment only from their RM or RM's RM and so on. Each employee has a fixed cost and a Leadership level.

You are a consultant tasked with selecting employees for a client. Each selected employee is to be paid a cost fixed for them. The total amount of cost to hire them should be within a budget. To make sure that Employees complete the client's work you choose a Manager, who is an employee that can assign tasks to all selected employees. The Manager may or may not be a selected employee, if he is not then he is not paid for.

You need to maximize the happiness level of the Client while making sure the cost is within a budget. The happiness of client is the equal to (Leadership level of the Manager * number of employees hired).

The following figure represents the company where each node is an employee and contains data (i, cost, leadership). The RM to employee relationship is represented by arrows. Let's say, Budget is 20.

The Client satisfication is maximum at 1200 when 2, 6, 7, or 4, 6, 7 are hired with 1 as the Manager in either case.

Input Format

You will process input from stdin. The first line contains an integer T, the number of testcases. T testcases follow. For each testcase, first line contains two numbers N, the number of employees and M, the budget. N lines follow, each line representing R[i], C[i], L[i] for ith employee (i starts from 1) denoting RM, cost and leadership respectively.