#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <climits>
#include<stdlib.h>
#include<time.h>



using namespace std;

struct problem_INSA
{
    int maszyna;
    int proces;
    int poprzednik_technologiczny;
    int nastepnik_technologiczny;
    int poprzednik_maszynowy;
    int nastepnik_maszynowy;
    int R;
    int Q;
    bool flaga_check;

    problem_INSA () : maszyna(), proces(), poprzednik_technologiczny(), nastepnik_technologiczny(), poprzednik_maszynowy(), nastepnik_maszynowy(), R(), Q(), flaga_check(false) {};
};

problem_INSA* problem;

queue<int> kolejka;

bool max_z_procesow(int a, int b) {
  return (problem[a].proces > problem[b].proces);
}

int main()
{
    ifstream wejscie;
    ofstream wyjscie1, wyjscie2;

    wejscie.open("bench_js.txt");
    wyjscie1.open("wyjscie1.txt");
    wyjscie2.open("wyjscie2.txt");

    unsigned int ile;
    wejscie >> ile;

    for (int hh = 1; hh <= ile; hh++)
    {
        string nazwa;

        int zadan, maszyn, wymiar_danych, maszyn_kopia, T = 0;

        wejscie >> nazwa >> zadan >> maszyn;

        wymiar_danych = zadan * maszyn;
        maszyn_kopia = maszyn;

        zadan++;
        maszyn++;
        wymiar_danych++;

        problem = new problem_INSA[wymiar_danych];
        int* pomoc = new int[wymiar_danych];
        int* maszynaproces = new int[maszyn];

        for (int i = 0; i < maszyn; i++)
        {
            maszynaproces[i] = 0;
        }

        pomoc[0] = 0;

        int k = 1;

        for (int i = 1; i < zadan; i++)
        {

            for (int j = 1; j < maszyn_kopia; j++)
            {
                wejscie >> problem[k].maszyna;
                wejscie >> problem[k].proces;

                problem[k].nastepnik_technologiczny = k + 1;

                if (j != 1)
                {
                    problem[k].poprzednik_technologiczny = k - 1;
                }

                pomoc[k] = k;
                k++;
            }

            wejscie >> problem[k].maszyna;
            wejscie >> problem[k].proces;

            problem[k].poprzednik_technologiczny = k - 1;
            pomoc[k] = k;
            k++;

            for (int j = 0; j <maszyn_kopia; j++)
            {
                problem[(i - 1) * maszyn_kopia + j + 1].R = problem[problem[(i - 1) * maszyn_kopia + j + 1].poprzednik_technologiczny].R + problem[(i - 1) * maszyn_kopia + j + 1].proces;
                problem[i * maszyn_kopia - j].Q = problem[problem[i * maszyn_kopia - j].nastepnik_technologiczny].Q + problem[i * maszyn_kopia - j].proces;
            }
        }

        int pozycja;
        int punkt_docelowy_optymalny = INT_MAX;
        int punkt_docelowy;
        int wskazana_pozycja;

        stable_sort(pomoc, pomoc+wymiar_danych, max_z_procesow);

        for (int i = 0; i < wymiar_danych; i++)
        {
            punkt_docelowy_optymalny = INT_MAX;
            wskazana_pozycja = maszynaproces[problem[pomoc[i]].maszyna];

            if (wskazana_pozycja == 0)
            {
                maszynaproces[problem[pomoc[i]].maszyna] = pomoc[i];
                problem[pomoc[i]].flaga_check = true;
            }
            else
            {
                punkt_docelowy_optymalny = problem[problem[pomoc[i]].poprzednik_technologiczny].R + max(problem[problem[pomoc[i]].nastepnik_technologiczny].Q, problem[wskazana_pozycja].Q);
                pozycja = 0;
            }

            while (wskazana_pozycja != 0)
            {
                punkt_docelowy = max(problem[problem[pomoc[i]].poprzednik_technologiczny].R, problem[wskazana_pozycja].R) + max(problem[problem[pomoc[i]].nastepnik_technologiczny].Q, problem[problem[wskazana_pozycja].nastepnik_maszynowy].Q);

                if (punkt_docelowy < punkt_docelowy_optymalny)
                {
                    punkt_docelowy_optymalny = punkt_docelowy;
                    pozycja = wskazana_pozycja;
                }

                wskazana_pozycja = problem[wskazana_pozycja].nastepnik_maszynowy;
            }

            if (!problem[pomoc[i]].flaga_check)
            {
                if (pozycja == 0)
                {
                    problem[maszynaproces[problem[pomoc[i]].maszyna]].poprzednik_maszynowy = pomoc[i];
                    problem[pomoc[i]].nastepnik_maszynowy = maszynaproces[problem[pomoc[i]].maszyna];
                    maszynaproces[problem[pomoc[i]].maszyna] = pomoc[i];
                    problem[pomoc[i]].flaga_check = true;
                }
                else
                {
                    problem[pomoc[i]].nastepnik_maszynowy = problem[pozycja].nastepnik_maszynowy;
                    problem[pomoc[i]].poprzednik_maszynowy = pozycja;
                    problem[problem[pozycja].nastepnik_maszynowy].poprzednik_maszynowy = pomoc[i];
                    problem[pozycja].nastepnik_maszynowy = pomoc[i];
                    problem[pomoc[i]].flaga_check = true;
                }
            }

            problem[0].nastepnik_maszynowy = 0;
            problem[0].poprzednik_maszynowy = 0;

            int Gtmp, popt;
            bool first = true;

            kolejka.push(pomoc[i]);

            while(!kolejka.empty())
            {
                Gtmp = kolejka.front();
                kolejka.pop();
                popt = problem[Gtmp].R;
                problem[Gtmp].R = max(problem[problem[Gtmp].poprzednik_technologiczny].R, problem[problem[Gtmp].poprzednik_maszynowy].R) + problem[Gtmp].proces;

                if (first || popt != problem[Gtmp].R)
                {
                    if (problem[Gtmp].nastepnik_maszynowy != 0)
                    {
                        kolejka.push(problem[Gtmp].nastepnik_maszynowy);
                    }

                    if (problem[Gtmp].nastepnik_technologiczny != 0)
                    {
                        kolejka.push(problem[Gtmp].nastepnik_technologiczny);
                    }
                }

                first = false;
            }


            kolejka.push(pomoc[i]);
            first = true;

            while(!kolejka.empty())
            {
                Gtmp = kolejka.front();
                kolejka.pop();
                popt = problem[Gtmp].Q;
                problem[Gtmp].Q = max(problem[problem[Gtmp].nastepnik_technologiczny].Q, problem[problem[Gtmp].nastepnik_maszynowy].Q) + problem[Gtmp].proces;

                if (first || popt != problem[Gtmp].Q)
                {
                    if (problem[Gtmp].poprzednik_maszynowy != 0)
                    {
                        kolejka.push(problem[Gtmp].poprzednik_maszynowy);
                    }

                    if (problem[Gtmp].poprzednik_technologiczny != 0)
                    {
                        kolejka.push(problem[Gtmp].poprzednik_technologiczny);
                    }
                }

                first = false;
            }
        }

        int tmp;

        for (int i = 1; i < maszyn;i++)
        {
            int jj = maszynaproces[i];

            while (jj != 0)
            {
                tmp = problem[jj].R+problem[jj].Q - problem[jj].proces;

                wyjscie1 << jj << " ";

                if (T < tmp)
                {
                    T = tmp;
                }

                jj = problem[jj].nastepnik_maszynowy;
            }

            wyjscie1 << endl;
        }

        wyjscie2 << nazwa << " " << T << endl;
    }


    wejscie.close();
    wyjscie1.close();
    wyjscie2.close();
}