#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<sstream>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
using namespace std;
struct  edge{
    int  e , next ;        
} edges[101000] ;
int  head[300] , ne , weight[300] ;
bool  used[300] , visit[300] ;
int  dp[300][300] , num[300] ;    
int  n , m ;
void  add_edge( int  a , int  b )
{
    edges[ne].e = b ;
    edges[ne].next = head[a] ;
    head[a] = ne ++ ;      
}
void  DFS( int now )
{
    int  temp = head[now] ;
    dp[now][0] = 0 ;
    num[now] = 1 ;
    visit[now] = true ;
    while( temp != -1 ){
        if( visit[edges[temp].e] ) continue ;
        DFS( edges[temp].e ) ;
        num[now] += num[edges[temp].e] ;
        temp = edges[temp].next ;    
    }
    temp = head[now];
    while( temp != -1 )
    {
        for( int  j = num[now] ; j >= 0 ; j -- )
        {
            for( int i = 0 ; j-i >= 0 ; i ++ )
            {
                 if( dp[now][j] > dp[now][j-i] + dp[edges[temp].e][i] )
                 dp[now][j] = dp[now][j-i] + dp[edges[temp].e][i] ;     
            }     
        }   
        temp = edges[temp].next ;       
    }
    if( weight[now] < dp[now][num[now]] )
    dp[now][num[now]] = weight[now] ;
    return ;      
}
int main()
{
    map<string,int> node;
    char  str[20100] ;
    string hold ;
    while( gets(str) ){
        if( !str[0] ) continue ;
        memset( head , -1 , sizeof(head) ) ;
        memset( used , false , sizeof(used) ) ;
        memset( dp , 11 , sizeof(dp) );
        memset( num , 0 , sizeof(num) );
        memset( visit , false , sizeof(visit) );
        ne = 0 ;
        int  top = 0 , father , son ;
        if( str[0] == '#' )
        break ;
        sscanf(str,"%d%d",&n,&m);
        for( int  i = 1 ; i <= n ; i ++ )
        {
             scanf("%s",str);
             if( node.find(str) == node.end() )
             {
                 node[str] = ++top;
                 father = top ;
             }   
             else
                 father = node[str] ;
             scanf("%d",&weight[father]);
             gets(str) ;
             stringstream ss(str) ;
             while( ss >> hold )
             {
                 if( node.find(hold) == node.end() )  
                 {
                     node[hold] = ++top ;
                     son = top ;  
                 }     
                 else
                     son = node[hold] ;
                 used[son] = true ;
                 add_edge(father,son);
             }
        }
        weight[0] = 999999999 ;
        for( int  i = 1;  i <= n ; i ++ )
        if( !used[i] )
        add_edge(0,i);
        DFS(0);
        int  ans = 999999999 ;
        //for( int  i = 0 ; i <= n ; i ++ )
        //{       
        //   for( int j = 0 ; j <= n+1 ; j ++ )
        //   {
        //        printf("%d ",dp[i][j]);    
        //    
        //   printf("\n"); 
        //}     }
        for( int  i = m ; i <= n ; i ++ )
        if( dp[0][i] < ans )
        ans = dp[0][i] ;
        printf("%d\n",ans) ;
    }    
}