Karen and Supermarket

/*
    Ideia 1:
    Vou criar uma lista de adjacencia no i, indicando quem que depende
    do i. O grafo formado tera a forma de arvore, ja que cada vertice tirando o
    1 tera um pai que eh menor do que ele.
    Nesta arvore, poderei utilizar um cupom se, e somente se, eu tiver utilizado os cupons
    de seus ancestrais.

    dp[i][k][f]: para o item i, qual o maior numero
    de itens que posso comprar usando k de dinheiro,
    sendo que se f eh 0 n posso usar o cupom e se f eh
    1 posso usar o cupom
    Para calcular a dp, calcularemos, em cada vertice, uma dp2[filhos][k][f]
    dp2[filho_i][k][f] = max(dp2[filho_i-1][k - x][f] + dp[filho_i][x][f])   -> Complexidade: O(N*B²)
    dp[i][k][0] = max(dp2[ultFilho][k][0], dp2[ultFilho][k - c[i]][0] + 1)   -> Complexidade: O(B)
    dp[i][k][1] = max(dp[i][k][0], dp2[ultFilho][k - c[i] + d[i]][1] + 1)    -> Complexidade: O(B)

    Resposta: max(dp[1][B][0], dp[1][B][1])

    Ideia 2:
    dp[i][t][f]: para o item i, qual o menor preco que tenho que pagar
    se quiser comprar t itens, sendo que se f eh 0 n posso usar cupom e
    se f eh 1 posso usar cupom

    Novamente, calcular uma dp2[filhos][t][f]
    dp2[filho_i][t][f] = min(dp2[filho_i-1][t-x][f] + dp[filho_i][x][f])    -> Complexidade: O(N³) -> usa o truque do sub -> O(N²)
    dp[i][t][0] = min(dp2[ultFilho][t][0], dp2[ultFilho][t-1][0] + c[i])    -> Complexidade: O(N)
    dp[i][t][1] = min(dp[i][t][0], dp2[ultFilho][t-1][1] + c[i] - d[i])     -> Complexidade: O(N)

    Complexidade: O(N³) (Mais facil), O(N²) (Com o truque)
    Resposta: Maximo t t.q. dp[1][t][1] <= B
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e3 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

int dp[MAXN][MAXN][2];
array<vector<int>, MAXN> grafo;
array<int, MAXN> c, d, tmp0, tmp1, sub;
int N, B;

void dfs(int v)
{
    sub[v] = 0;
    for (int i = 1; i <= N; i++) dp[v][i][0] = dp[v][i][1] = INF;

    for (auto viz : grafo[v])
    {
        dfs(viz);

        tmp0.fill(INF); tmp1.fill(INF);
        for (int i = 0; i <= min(N, sub[v]); i++)
        {
            for (int j = 0; j <= min(N, sub[viz]) && i + j <= N; j++)
            {
                tmp0[i+j] = min(tmp0[i+j], dp[v][i][0] + dp[viz][j][0]);
                tmp1[i+j] = min(tmp1[i+j], dp[v][i][1] + dp[viz][j][1]);
            }
        }
        sub[v] += sub[viz];

        for (int i = 0; i <= min(N, sub[v]); i++)
        {
            dp[v][i][0] = tmp0[i];
            dp[v][i][1] = tmp1[i];
        }
    }
    ++sub[v];
    for (int i = N; i >= 1; i--)
    {
        dp[v][i][0] = min(dp[v][i][0], dp[v][i-1][0] + c[v]);
        dp[v][i][1] = min(dp[v][i][0], dp[v][i-1][1] + c[v] - d[v]);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> B;
    for (int i = 1; i <= N; i++)
    {
        cin >> c[i] >> d[i];
        if (i != 1)
        {
            int X;
            cin >> X;
            grafo[X].push_back(i);
        }
    }
    dfs(1);

    for (int i = N; i >= 0; i--) if (dp[1][i][1] <= B) {cout << i << '\n'; break;}
}