#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];

int sumT[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 calcT(int v) {
    if(sumT[v] != -1)
        return sumT[v];
    
    sumT[v] = 0;
    if(t[v]) sumT[v] ++;
    if(le[v] != -1) sumT[v] += calcT(le[v]);
    if(ri[v] != -1) sumT[v] += calcT(ri[v]);
    return sumT[v];
}

int calc(int v, int r) {
    if(used[v][r])
        return dp[v][r];
    
    if(t[v] && !r) {
        used[v][r] = true;
        return dp[v][r] = -INF;
    }
    
    if(t[v]) {
        used[v][r] = true;
        if(ri[v] == -1) return dp[v][r] = 0;
        return dp[v][r] = calc(ri[v], r - 1);
    }
    
    if(le[v] == -1 && ri[v] == -1) {
        used[v][r] = true;
        return dp[v][r] = 1;
    }
    
    if(r > calcT(v)) {
        used[v][r] = true;
        return dp[v][r] = calc(v, calcT(v));
    }
    
    if(le[v] == -1) {
        used[v][r] = true;
        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));
        return dp[v][r] = t;
    }
    
    if(r) 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;
    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;
    }
    
    memset(sumT, -1, sizeof(sumT));
    
    cout << 1 + calc(le[1], k) << endl;
}

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

    return 0;
}
