#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>

#define MAXN 5006
#define MV 134744072

using namespace std;

int p[MAXN],parent[MAXN],dp[2][MAXN][MAXN],boy[MAXN];

vector <int> a[MAXN];

int q[MAXN];

void bfs()
{
    int read=1,write=2;
    q[1] = 1;
    while ( read < write )
    {
        int curr = q[read];
        read++;
        for ( int i=0; i<a[curr].size(); i++ )
        {
            int neigh = a[curr][i];
            q[write] = neigh;
            write++;
        }
    }
}

int main()
{
    int n,k,i;
    scanf ("%d%d",&n,&k);
    for ( i=2; i<=n; i++ )
    {
        scanf ("%d%d",&parent[i],&boy[i]);
        a[ parent[i] ].push_back( i );
    }
    
    bfs();
    
    memset(dp,8,sizeof(dp));
    
    for ( i=1; i<=n; i++ )
    {
        if ( a[ i ].size() ) dp[0][i][0] = 0;
        //if ( boy[i] ) dp[0][i][1] = 0;
    }
    
    for ( i=n; i>=1; i-- )
    {
        int curr = q[i];
        int par = parent[curr];
        
        for ( int j=0; j<=k; j++ )
            if ( dp[ p[curr] ][curr][j] != MV ) dp[ p[curr] ][curr][j]++;

        if ( curr == 1 ) break;    
        
            for ( int j=0; j<=k; j++ )
                if ( dp[ p[par] ][par][j] != MV )
                { dp[ p[par]^1 ][par][j+1] = dp[ p[par] ][par][j]; }
                
        if ( !boy[curr] )
        {
        
            for ( int j=0; j<=k; j++ )
                for ( int l=0; l<=k; l++ )
                    if ( dp[ p[par] ][par][l] != MV && dp[ p[curr] ][curr][j] != MV )
                    {
                        if ( dp[ p[par]^1 ][par][l+j] == MV || dp[ p[par]^1 ][par][l+j] < dp[ p[par] ][par][l] + dp[ p[curr] ][curr][j] )
                            dp[ p[par]^1 ][par][l+j] = dp[ p[par] ][par][l] + dp[ p[curr] ][curr][j];
                    }
        }
        
        p[par] ^= 1;
           
        memset(dp[ p[par]^1 ][par],8,sizeof( dp[ p[par]^1 ][par] ));
    }
    
    int maxi = 0;
    for ( int j=0; j<=k; j++ )
        if (  dp[ p[1] ][1][j] != MV && dp[ p[1] ][1][j] > maxi ) maxi = dp[ p[1] ][1][j];
    
    printf ("%d\n",maxi);
}