#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 5010
int dp[MAXN][MAXN];
int father[MAXN];
vector<int> spis[MAXN];
int forbidden[MAXN];
int tocut[MAXN];
int n,k;
void DFS(int v)
{
    for(int i=0;i<=n;i++)
        if(dp[father[v]][i]) dp[v][i]=dp[father[v]][i]+1;
    for(int i=0;i<spis[v].size();i++)
    {
        int t=spis[v][i];
        if(forbidden[t])
        {
            for(int i=n;i>0;i--) dp[v][i]=dp[v][i-1];
            dp[v][0]=0;
            tocut[v]=1;
            continue;
        }
        DFS(t);
        if(tocut[t]==0) for(int i=0;i<=n;i++) if(dp[v][i]<dp[t][i]) dp[v][i]=dp[t][i];
        if(tocut[t])
        {
            for(int i=n;i>0;i--) dp[v][i]=max(dp[t][i],dp[v][i-1]);
            dp[v][0]=0;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    int a,b;
    for(int i=2;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        father[i]=a;
        spis[a].push_back(i);
        forbidden[i]=b;
    }
    dp[1][0]=1;
    DFS(1);
    int ans=0;
    for(int i=0;i<=k;i++) if(dp[1][i]>ans) ans=dp[1][i];
    printf("%d\n",ans);
}
