#include <bits/stdc++.h>

 #define pii pair<int,int>

 #define max(x,y) (x>y?x:y)

 #define min(x,y) (x<y?x:y)

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=;

 struct node

 {

     int from,to,val,next;

     node(){};

     node(int from,int to,int val,int next):from(from),to(to),val(val),next(next){};

 }edge[N];

 int head[N], n, edge_cnt;

 void add_node(int from,int to,int val)

 {

     edge[edge_cnt]=node(from, to, val, head[from]);

     head[from]=edge_cnt++;

 }

 int dp[N][N];

 int DFS(int t,int m,int val)

 {

     if(m==)    return ;   //点数上限了。

     dp[t][]=val;           //只能挑1个点时，必须挑自己

     node e;

     int sum=;

     for(int i=head[t]; i!=-&&m>; i=e.next)

     {

         e=edge[i];

         int tmp=DFS(e.to, m-, e.val);  //最多可以在e.to子树中选多少个点

         sum+=tmp;

         for(int j=sum; j>; j--)

             for(int k=; k<=tmp&& k<j; k++) //保证j-k>=1，因为t是必选的

                 if(dp[t][j-k]>=)

                     dp[t][j]=max(dp[t][j], dp[t][j-k]+dp[e.to][k]);

     }

     return sum; //返回在本子树中可以选的点数上限

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int a,b,m;

     while(scanf("%d%d",&n,&m),n+m)

     {

         memset(head, -, sizeof(head));

         memset(dp, -, sizeof(dp));

         edge_cnt=;

         for(int i=; i<=n; i++)

         {

             scanf("%d%d",&a,&b);

             add_node(a,i,b);

         }

         DFS(, m+, ); //0是虚拟根

         printf("%d\n", dp[][m+]);

     }

     return ;

 }