#include <iostream>
#include <vector>
#include <algorithm>
unsigned vSize[8192], mustCut[8192];
typedef std::pair<unsigned, unsigned> Pair;
std::vector<unsigned> children[8192];
inline 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;
        }else break;
        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-children[me].size()+1+i);
        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];
bool dfs(unsigned i){
    bool hb=false;
    vSize[i]=1;
    std::vector<unsigned> c;
    for(unsigned j=0;j<children[i].size();j++){
        if(bad[children[i][j]]){
            mustCut[i]++;
            hb=true;
        }else if(dfs(children[i][j])){
            hb=true;
            c.push_back(children[i][j]);
        }else{
            vSize[i]+=vSize[children[i][j]];
        }
    }
    children[i].swap(c);
    return hb;
}
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--;
        bad[i]=b;
        children[a].push_back(i);
    }
    dfs(0);
    std::vector<Pair> r;
    min(r, 0, K);
    std::cout<<r.back().second<<'\n';
    return 0;
}
