#include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int N,M,tl[],tr[],f[][],num[],con[];

 void insect(int fa,int now)

 {

     if (tl[fa]==)

      {tl[fa]=now;}

     else

      {

          int i=tl[fa];

          while (tr[i]!=) i=tr[i];

          tr[i]=now;

      }

 }

 void dfs(int x)

 {

     if (tr[x]!=) dfs(tr[x]);

     if (tl[x]!=) dfs(tl[x]);

     con[x]=con[tr[x]]+con[tl[x]]+;

     int i,j;

     f[x][]=num[x];

     for (i=;i<=con[tr[x]];++i)

     {

         f[x][i]=max(f[x][i],f[tr[x]][i]);

         for (j=;j<=con[tl[x]];++j)

          f[x][i+j+]=max(f[x][i+j+],num[x]+f[tr[x]][i]+f[tl[x]][j]);

     }

 }

 int main()

 {

     memset(f,,sizeof(f));

     memset(tl,,sizeof(tl));

     memset(tr,,sizeof(tr));

     memset(con,,sizeof(con));

     memset(num,,sizeof(num));

     scanf("%d %d\n",&N,&M);

     int i,j,x,y;

     for (i=;i<=N;++i)

     {

         scanf("%d %d\n",&x,&num[i]);

         insect(x,i);

     }

     dfs(tl[]);

     printf("%d\n",f[tl[]][M]);

 }