#include <iostream>
#include <iterator>
#include <map>

using namespace std;

void swap(long *xp, long *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void bubbleSort(long arr[], int n)
{
    int i, j;
    for (i = 0; i < n-1; i++)
    {
        for (j = 0; j < n-i-1; j++)
        {
            if (arr[j] > arr[j+1])
            {
                swap(&arr[j], &arr[j+1]);
            }
        }

    }

}


int main() {
    int t;
    cin >> t;
    for(int c=0;c<t;c++)
    {
        // Input
        long B;
        int n;
        cin>> B >>n;
        int k[n];
        int max=0;
        for(int i=0;i<n;i++)
        {
            cin>>k[i];
            if(k[i]>max)
            {
                max=k[i];
            }
        }
        long val[n][max];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<k[i];j++)
            {
                cin>>val[i][j];
            }
        }

        // Sorting
        for (int i=0;i<n;i++)
        {
            bubbleSort(val[i],k[i]);
        }

        // Calculations
cout << "Picking the cheapest components." << endl;
        multimap<long, int> pos;
        long b = B;
        for(int i=0;i<n;i++)
        {
            b = b - val[i][0];
            for(int j=k[i]-1;j>=0;j--)
            {
                val[i][j] = val[i][j] - val[i][0];
                if(val[i][j]>0)
                {
                    pos.insert(pair<long, int>(val[i][j], i));
                }
            }
        }
cout << "Remaining budget is: " << b << endl;

        // Negative Check
        if (b<0)
        {
cout << "There are no possible anwsers." << endl;
            cout << "0";
            return 0;
        }
cout << "There are possible anwsers." << endl;
cout << "Cost map is: " << endl;
for (auto itr = pos.crbegin(); itr != pos.crend(); ++itr)
{
    cout << itr->first << " " << itr->second << endl;
}
        // Removing entries after budget change
        LOOP1:for (auto itr = pos.crbegin(); itr != pos.crend(); ++itr)
        {
            long key = itr->first;
            if (key>b){
cout << "Removing entry bigger than remaining budget: ";
cout << key << endl;
                pos.erase(key);
                goto LOOP1;
            }
        }

        // Checking for solution
cout << "Checking if map is empty: ";
        if (pos.empty())
        {
cout << "(empty)" << endl;
cout << "Budget spent is: " << endl;
            cout << B - b;
            return 0;
        }
cout << "Map is not empty, more money can be spent." << endl;

        // auto itr = pos.begin();
        // int key = itr->first;
        // int value = itr->second;
        // LOOP2:for (auto itr = pos.begin(); itr != pos.end(); ++itr)
        // {
        //     int temp = itr->second;
        //     if (temp == value)
        //     {
        //         pos.erase(itr);
        //         goto LOOP2;
        //     }
        // }
        // cout << "Removing " << key << " from line " << value << endl;
        // b = b - key;
        // for(int j=k[value]-1;j>=0;j--)
        // {
        //     val[value][j] = val[value][j] - key;
        //     if(val[value][j]>0)
        //     {
        //         pos.insert(pair<int, int>(val[value][j], value));
        //     }
        // }
        // goto LOOP1;
    }
    return 0;
}