#include <iostream>
#include <vector>
#include <algorithm>
unsigned vSize[8192], mustCut[8192];
typedef std::pair<unsigned, unsigned> Pair;
std::vector<unsigned> children[8192];
void newmax(unsigned &a, unsigned b){
    if(b>a) a=b;
}
void merge(std::vector<Pair> &res, const std::vector<Pair> &a, const std::vector<Pair> &b, unsigned k){
    static bool pos[8129];
    static unsigned max[8192];
    for(unsigned x=0;x<=k;x++) pos[x]=max[x]=0;
    for(unsigned x=0;x<a.size();x++){
        if(a[x].first+1<=k){
            newmax(max[a[x].first+1], a[x].second);
            pos[a[x].first+1]=1;
        }
        for(unsigned y=0;y<b.size();y++){
            if(a[x].first+b[y].first>k) break;
            pos[a[x].first+b[y].first]=1;
            newmax(max[a[x].first+b[y].first], a[x].second+b[y].second);
        }
    }
    for(unsigned x=0;x<=k;x++) if(pos[x]){
        if(res.empty()) res.push_back(Pair(x, max[x]));
        else res.push_back(Pair(x, std::max(max[x], res.back().second)));
    }
    return;
}
void min(std::vector<Pair> &res, unsigned me, unsigned k){
    //std::cout<<me<<'c'<<mustCut[me]<<'v'<<vSize[me]<<'k'<<k<<'\n';
    if(k<children[me].size()+mustCut[me]) return;
    res.push_back(Pair(mustCut[me],vSize[me]));
    for(unsigned i=0;i<children[me].size();i++){
        std::vector<Pair> next;
        min(next, children[me][i], k-children[me].size()+1);
        std::vector<Pair> tmp;
        merge(tmp, res, next, k);
        tmp.swap(res);
    }
    //for(unsigned i=0;i<res.size();i++){
    //    std::cout<<me<<' '<<res[i].first<<'='<<res[i].second<<'\n';
    //}
    return;
}
bool bad[8192], hasBad[8192];
unsigned parent[8192];
void flag(unsigned i){
    bad[i]=true;
    mustCut[parent[i]]++;
    while(i!=0){
        if(hasBad[i]) break;
        hasBad[i]=true;
        i=parent[i];
    }
    hasBad[0]=true;
    return;
}
bool clearCheck(unsigned i){
    //return !hasBad[i];
    return false;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    unsigned N, K;
    std::cin>>N>>K;
    for(unsigned i=1;i<N;i++){
        unsigned a, b;
        std::cin>>a>>b;
        a--;
        parent[i]=a;
        if(b) flag(i);
        else children[a].push_back(i);
    }
    for(unsigned i=N;i--;){
        unsigned k=std::remove_if(children[i].begin(), children[i].end(), clearCheck)-children[i].begin();
        vSize[i]=1;
        for(unsigned j=k;j<children[i].size();j++){
            vSize[i]+=vSize[children[i][j]];
        }
        children[i].erase(children[i].begin()+k, children[i].end());
    }
    std::vector<Pair> r;
    min(r, 0, K);
    std::cout<<r.back().second<<'\n';
    return 0;
}
