#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>

#define pb push_back

using namespace std;

const int MAXN = 5005;
const int INF = 200000;

int n, k;
vector<int> g[MAXN];
int t[MAXN];
bool used[MAXN][MAXN];
int dp[MAXN][MAXN];
int ri[MAXN], le[MAXN];

void read() {
    int par;
    
    scanf("%d %d", &n, &k);
    for(int i = 2; i <= n; i ++) {
        scanf("%d %d", &par, &t[i]);
        g[par].pb(i);
    }
}

bool cmp(int a, int b) {
    if(t[a] != t[b]) return t[a] > t[b];
    return a < b;
}

int calc(int v, int r) {
    if(used[v][r])
        return dp[v][r];
    
    if(t[v] && !r) {
        used[v][r] = true;
//        cout << v << " " << r << " " << -INF << endl;
        return dp[v][r] = -INF;
    }
    
    if(t[v]) {
        used[v][r] = true;
        
        if(ri[v] == -1) {
//            cout << v << " " << r << " " << 0 << endl;
            return dp[v][r] = 0;
        }
//        int tmp = calc(ri[v], r - 1);
//        cout << v << " " << r << " " << tmp << endl;
        return dp[v][r] = calc(ri[v], r - 1);
    }
    
    if(le[v] == -1 && ri[v] == -1) {
        used[v][r] = true;
//        cout << v << " " << r << " " << 1 << endl;
        return dp[v][r] = 1;
    }
    
    if(le[v] == -1) {
        used[v][r] = true;
//        int tmp = 1 + calc(ri[v], r);
//        cout << v << " " << r << " " << tmp << endl;
        return dp[v][r] = 1 + calc(ri[v], r);
    }
    
    int t = -INF;
    
    if(ri[v] == -1) {
        used[v][r] = true;
        if(r) t = 0;
        t = max(t, 1 + calc(le[v], r));
//        cout << v << " " << r << " " << t << endl;
        return dp[v][r] = t;
    }
    
    t = calc(ri[v], r - 1);
    
    for(int i = 0; i <= r; i ++)
        t = max(t, 1 + calc(le[v], i) + calc(ri[v], r - i));
    
    used[v][r] = true;
//    cout << v << " " << r << " " << t << endl;
    return dp[v][r] = t;
}

void solve() {
    for(int i = 1; i <= n; i ++)
        if(g[i].size() > 1)
            sort(g[i].begin(), g[i].end(), cmp);
    
    memset(ri, -1, sizeof(ri));
    memset(le, -1, sizeof(le));
    
    for(int i = 1; i <= n; i ++)
        if(g[i].size() > 0) {
            le[i] = g[i][0];
            for(int j = 0; j < g[i].size() - 1; j ++)
                ri[ g[i][j] ] = g[i][j + 1];
        }
    
    if(le[1] == -1) {
        cout << 1 << endl;
        return;
    }
    
    cout << 1 + calc(le[1], k) << endl;
}

int main()
{
    read();
    solve();

    return 0;
}
