// CCC 2002
// Problem S4: Bridge Crossing

// This uses a Dynamic Programming approach, due to Vassili Skarine.
// the key is a best array: best[i] holds the best time for the first i
// people. also group[i] holds the length of the group with i as the
// last person.

// essentially all the various combinations are tested in the following
// order (assuming m = 3 for example)
// a
// ab
// abc
//
// a b
// a bc
// a bcd
//
// ab c
// ab cd
// ab cde
// ...

import java.awt.*;
import hsa.*;

public class S4BridgeCrossingDP
{

    public static void main (String [] args)
    {
	TextInputFile fi = new TextInputFile ("bridge4.in");
	TextOutputFile c = new TextOutputFile ("bridge4.out");
	String [] name;
	int [] time;
	int m, n;
	int totalTime = 0;

	// read info;
	m = fi.readInt ();
	n = fi.readInt ();
	name = new String [n];
	time = new int [n];
	for (int i = 0 ; i < n ; i++)
	{
	    name [i] = fi.readLine ();
	    time [i] = fi.readInt ();
	}
	fi.close ();

	// determine the best times
	int [] best = new int [n + 1];
	int [] group = new int [n + 1];
	for (int i = 0 ; i < n + 1 ; i++)
	{
	    best [i] = 1000000;
	    group [i] = -1;
	}
	best [0] = 0;
	group [0] = 0;
	for (int i = 0 ; i < n + 1 ; i++)
	{
	    int cur = 0;
	    for (int j = 1 ; j <= m && i + j - 1 < n ; j++)
	    {
		cur = Math.max (cur, time [i + j - 1]);
		if (best [i] + cur < best [i + j])
		{
		    best [i + j] = best [i] + cur;
		    group [i + j] = j;
		}
	    }
	}

	c.println ("Total Time: " + best [n]);

	// to get the groups, work backward thru group creating
	// the dividing lines. Then use those lines (in reverse order)
	// to print the solution.
	int [] lines = new int [n + 1];
	int k = n;
	int x = 0;
	while (group [k] != 0)
	{
	    lines [x++] = group [k];
	    k = k - group [k];
	}
	int z = 0;
	for (int i = x - 1 ; i >= 0 ; i--)
	{
	    for (int j = 0 ; j < lines [i] ; j++)
		c.print (name [z++] + " ");
	    c.println ();
	}

	c.close ();
    }
}