#include<bits/stdc++.h>
using namespace std;
struct node{
    string s;
    int w;
    node(const string& s,const int& w):s(s),w(w){}
    bool operator < (const node& o)const{
        if(w==o.w)return s<o.s;
        return w>o.w;
    }
};
void solve(){
    int n,m;
    cin>>n>>m;
    vector<node> a;
    for(int i=0;i<n;i++){
        string s;
        int w;
        cin>>s>>w;
        a.push_back(node(s,w));
    }
    sort(a.begin(),a.end());
    long long ans=0;
    for(int i=0;i<m;i++){
        ans+=1ll*a[i].w*(m-i);
    }
    cout<<ans<<" ";
    for(int i=0;i<m;i++){
        cout<<a[i].s;
        if(i==m-1)cout<<'\n';
        else cout<<' ';
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}