#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;
vector <int > v[5005];
int dp[5005][5005];
int N, K;
int isBad[5005], bad[5005];
int prenum[5005], cnt;
vector <int> s[5005];

void scan(){
    scanf ( "%d%d", &N, &K);
    
    for ( int i = 2; i <= N; ++i ){
        int father;
        scanf ( "%d%d", &father, isBad + i );
        v[father].push_back ( i );
    }
}

void dfs ( int i ){
   // cout << i << endl;
    prenum[i] = ++cnt;
    
    for ( int j = 0; j < (int)v[i].size(); ++j )
        dfs ( v[i][j] );
    if ( i != 1 ) s[prenum[i]].push_back ( cnt );
    //cout << prenum[i] << " " << cnt << endl;
}

inline int MAX ( int t1, int t2 ){
    return ( t1 > t2 ) ? t1 : t2;
}

int go ( int i, int k ){
    if ( k > K )
        return -1e9;
    if ( i == N + 1 )
        return 0;
    
    
    if ( dp[i][k] != -1 )
        return dp[i][k];
    dp[i][k] = -1e9;
    if ( !bad[i] )
        dp[i][k] = go ( i + 1, k ) + 1;
    
    for ( int j = 0; j < s[i].size(); ++j )
        dp[i][k] = MAX ( dp[i][k], go ( s[i][j] + 1, k + 1 ) ) ;
 //   cout << i << " " << k << " " << dp[i][k] << endl;
    
    return dp[i][k];
}
void solve(){
    dfs ( 1 );
    for ( int i = 1; i <= N; ++i )
        bad[ prenum[i] ] = isBad[i];
 //   for ( int i =1 ; i <= N; ++i )
    //    cout << i << " " << bad[i] << endl;
        
    
    for ( int i = 0; i < 5005; ++i ) for ( int j = 0; j < 5005; ++j ) dp[i][j] = -1e9;
    for ( int i = 0; i <= K; ++i )
        dp[N + 1][i] = 0;
    
    for ( int i = N; i >= 1; --i ){
        for ( int j = 0; j <= K; ++j ){
            if ( !bad[i] )
                dp[i][j] = dp[i + 1][j] + 1;
            if ( j != K )
                for ( int p = 0; p < s[i].size(); ++p )
                    if ( dp[i][j] < dp[ s[i][p] + 1][j + 1] )
                        dp[i][j] = dp[ s[i][p] + 1][j + 1];
        }
    }
    
    cout << dp[1][0] << endl;  
}


int main(){
    scan();
    solve();
}