//34次csp 文本分词 40
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2, 3, "Ofast", "inline")
using namespace std;

const int N=270000+10,M=10010;
//左右端点0~19999
int idx=20001,duandian=0;
int l[N],r[N]; //duandian/2+1 为单词数
string e[N];

vector<string> dancibiao;  //记录答案
unordered_map<int,int> jiedian_danci; //统计每个节点属于的单词
unordered_map<string,pair<string,string>> dancizucheng;//每个组合的前半边与后半边
priority_queue<pair<int,string>> dagendui;
unordered_map<string,int> rongyu;  //每次由新的组合更改双链表之后 组合的前一个字母与前 组合的后一个字母与后就是冗余数据
unordered_map<string,set<int>> pinjiepos; //一个组合 前半段结点所在的位置

int n,m;  //n 单词  m 规定词汇表所需个数

typedef pair<int,pair<int,string>>  PIIS;

struct Danci
{
    int left,right;
    int pinlv;
}dc[M];
//在编号为k的节点之后插入
void add(int k,string x)
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx++;
}
void chutai()
{

    set<string> tongji; //统计所有单个字母 且是升序排序
    unordered_map<string,int> cishu;//记录新生成的序列次数 随后添加到优先队列中
    for(int c=1;c<=n;c++)
    {
        string danci;
        cin>>danci>>dc[c].pinlv;
        dc[c].left=duandian;
        dc[c].right=duandian+1;
        //初始化双链表
        l[dc[c].right]=dc[c].left;
        r[dc[c].left]=dc[c].right;
        duandian+=2;

        string zuhe="";//记录每一次生成的新序列  为单词有重复字母作依据

        for(int i=0;i<danci.size();i++)
        {
            jiedian_danci[idx]=c;
            string str=string(1,danci[i]);
            int pos=idx;//当前结点的idx
            add(l[dc[c].right],str);
            tongji.insert(str);

            //记录组合次数
            //记录每个组合首个字符对应的节点
            if(i+1<danci.size())
            {
                string pinjie;
                pinjie=string(1,danci[i])+string(1,danci[i+1]);
                if(pinjie==zuhe)
                {
                    //存在至少连续3个重复单词
                    zuhe="";
                }
                else
                {
                    zuhe=pinjie;
                    pinjiepos[pinjie].insert(pos);
                    if(!dancizucheng.count(pinjie))
                        dancizucheng[pinjie]={string(1,danci[i]),string(1,danci[i+1])};
                    cishu[pinjie]+=dc[c].pinlv;
                }
            }
        }
    }
    for(auto t:cishu) 
        dagendui.push({t.second,t.first});
    for(auto t:tongji)
        dancibiao.push_back(t);
    /*
    //1、dc中的左右端点和频次
    for(int i=1;i<=n;i++)
      cout<<dc[i].left<<" "<<dc[i].right<<" "<<dc[i].pinlv<<endl;
    */
    /*
    //2、组合中前半段节点的位置  测试能否删除
    for(auto t:pinjiepos)
    {
        cout<<t.first;
        set<int> v=t.second;
        if(t.first=="cu") v.erase(20001);
        for(auto w:v) cout<<w<<" ";
        cout<<endl;
    }
    */
    /*
    //3、组合的前半段和后半段字母
    for(auto t:dancizucheng)
        cout<<t.first<<" "<<t.second.first<<" "<<t.second.second<<endl;
    */
    /*
    //4、组合的频次
    for(auto t:cishu) 
        cout<<t.second<<" "<<t.first<<endl;
    */
    /*
    //5、每个节点属于哪个单词
    for(auto t:jiedian_danci)
        cout<<t.first<<" "<<t.second<<endl;
    */

    /*
    //6、词汇表中的词汇
    for(auto t:dancibiao)
        cout<<t<<endl;
    */

    /*
    //7、遍历双链表
    for(int c=1;c<=n;c++)
    {
        int left=dc[c].left,right=dc[c].right;
        for(int i=r[left];i!=right;i=r[i])
            cout<<i<<" ";
        cout<<endl;
    }
    */

}
bool allone()
{
    for(int i=1;i<=n;i++)
    {
        int left=dc[i].left,right=dc[i].right;
        //cout<<left<<right<<endl;
        //cout<<r[r[left]]<<" "<<right<<endl;
        if(r[r[left]]!=right)
            return false; 
    }
    return true;
}

string paochu()
{
    auto ding=dagendui.top();
    dagendui.pop();
    //消除堆顶的冗余数据
    while(rongyu.count(ding.second))
    {
        ding.first-=rongyu[ding.second];
        rongyu.erase(ding.second);
        dagendui.push({ding.first,ding.second});

        ding=dagendui.top();
        dagendui.pop();
    }
    vector<string> ans;
    int num=ding.first;
    string str=ding.second;
    ans.push_back(str);

    //测试
    //cout<<str<<" "<<num;


    while(dagendui.size()!=0&&dagendui.top().first==num)
    {
        ding=dagendui.top();
        dagendui.pop();
        if(rongyu.count(ding.second))
        {
            ding.first-=rongyu[ding.second];
            rongyu.erase(ding.second);
            dagendui.push({ding.first,ding.second});
        }
        else
        {
            ans.push_back(ding.second);
        }
    }
    string res;

    if(ans.size()==1) 
        return ans[0];
    else
    {
        priority_queue<PIIS,vector<PIIS>,greater<PIIS>> h;
        for(int i=0;i<ans.size();i++)
            h.push({ans[i].size(),{dancizucheng[ans[i]].first.size(),ans[i]}});
        res=h.top().second.second;
        h.pop();
        while(h.size()!=0)
        {
            string str=h.top().second.second;
            h.pop();
            dagendui.push({num,str});
        }
    }
    return res;
}
//删除a节点
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}
void hebing_shanchu(set<int> pos)
{
    vector<int> xulie;
    for(auto t:pos)
        xulie.push_back(t);
    bool is_chongfu=false;
    for(int i=0;i<xulie.size();i++)
    {

        if(!is_chongfu&&l[xulie[i]]>20000)
        {
            string str=e[l[xulie[i]]]+e[xulie[i]];
            rongyu[str]+=dc[jiedian_danci[xulie[i]]].pinlv;
            pinjiepos[str].erase(l[xulie[i]]);
            /*
            //测试 删除的冗余点
            cout<<l[xulie[i]]<<endl;
            auto t=pinjiepos[str];
            cout<<str<<" ";
            for(auto p:t)
                cout<<p<<" ";
            cout<<endl;
            */
        }
        if(r[r[xulie[i]]]==xulie[i+1])
        {
            is_chongfu=true;
        }
        else
        {
            is_chongfu=false;
            int pos=r[xulie[i]];
            if(r[pos]>20000)
            {
                string str=e[pos]+e[r[pos]];
                rongyu[str]+=dc[jiedian_danci[pos]].pinlv;
                pinjiepos[str].erase(pos);
                /*
                //测试 删除的冗余点
                cout<<pos<<endl;
                auto t=pinjiepos[str];
                cout<<str<<" ";
                for(auto p:t)
                    cout<<p<<" ";
                cout<<endl;
                */
            }
        }
        e[xulie[i]]+=e[r[xulie[i]]];
        remove(r[xulie[i]]);    
    }
    /*
    //测试冗余数据
    for(auto t:rongyu)
        cout<<t.first<<" "<<t.second<<endl;
    */
   /*
    //测试合并之后
    for(int i=1;i<=n;i++)
    {
        int left=dc[i].left,right=dc[i].right;
        for(int j=r[left];j!=right;j=r[j])
            cout<<e[j]<<" ";
        cout<<endl;
    }
    */
}
void zeng(set<int> pos)
{
    //连续的位置
    vector<int> xulie;
    vector<int> p;
    for(auto t:pos)
        p.push_back(t);

    int i=0,j=0;
    unordered_map<string,int> tongji;
    for(;i<p.size();)
    {
        //找出节点相邻的位置
        xulie.clear();
        if(l[p[i]]>20000)
            xulie.push_back(l[p[i]]);
        xulie.push_back(p[i]);
        for(j=i+1;j<p.size();)
        {
            if(r[xulie.back()]==p[j]&&j<p.size())
            {
                xulie.push_back(p[j]);
                j++;
            }
            else break;
        }
        i=j;
        if(r[xulie.back()]>20000)
            xulie.push_back(r[xulie.back()]);
        /*
        //测试 连续序列正确性
        for(auto t:xulie)
            cout<<t<<" ";
        cout<<endl;
        */

        //添加
        string zuhe="";

        for(int i=0;i<xulie.size();i++)
        {
            if(i+1<xulie.size())
            {
                string pinjie=e[xulie[i]]+e[xulie[i+1]];
                if(pinjie!=zuhe)
                {
                    zuhe=pinjie;
                    tongji[pinjie]+=dc[jiedian_danci[xulie[i]]].pinlv;
                    if(!dancizucheng.count(pinjie))
                    {
                        dancizucheng[pinjie]={e[xulie[i]],e[xulie[i+1]]};
                        /*
                        //测试单词组成
                        cout<<pinjie<<" "<<e[xulie[i]]<<" "<<e[xulie[i+1]]<<endl;
                        */
                    }
                    pinjiepos[pinjie].insert(xulie[i]);
                    /*
                    //测试拼接位置
                    cout<<pinjie<<" "<<xulie[i]<<endl;
                    */
                }
                else
                {
                    zuhe="";
                }
            }
        }

    }

    for(auto t:tongji)
    {
        dagendui.push({t.second,t.first});
        /*
        //测试统计数据
        cout<<t.first<<" "<<t.second<<endl;
        */
    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    chutai();
    //cout<<allone()<<endl;

    while(dancibiao.size()<m&&!allone())
    {
        string xincihui=paochu();
        dancibiao.push_back(xincihui);

        hebing_shanchu(pinjiepos[xincihui]);

        zeng(pinjiepos[xincihui]);
        pinjiepos.erase(xincihui);
    }

    for(auto t:dancibiao)
        cout<<t<<endl;

    return 0;
}