//
// Written by Fyodor Menshikov 10.03.2009
// 13:02-13:23
//

import java.io.*;
import java.util.*;

class Query {

   int id;
   int start;
   int finish;
   int room = 0;

   void asserT(boolean e) {
      if (!e) {
         throw new Error();
      }
   }

   Query(int id, Scanner in) {
      this.id = id;
      int h0 = in.nextInt();
      int m0 = in.nextInt();
      int h1 = in.nextInt();
      int m1 = in.nextInt();
      asserT(0 <= h0 && h0 < 24);
      asserT(0 <= m0 && m0 < 60);
      asserT(0 <= h1 && h1 < 24);
      asserT(0 <= m1 && m1 < 60);
      start = h0 * 60 + m0;
      finish = h1 * 60 + m1;
      asserT(start < finish);
   }

   static class SortByFinish implements Comparator<Query> {

      public int compare(Query first, Query second) {
         return first.finish - second.finish;
      }
   }

   static class SortById implements Comparator<Query> {

      public int compare(Query first, Query second) {
         return first.id - second.id;
      }
   }
}

public class Main {

   Scanner in;
   PrintWriter out;

   void solve() {
      in.useDelimiter("\\s+|-|\\:");
      int rooms[] = new int[1 + in.nextInt()];
      Query queries[] = new Query[in.nextInt()];
      for (int i = 0; i < queries.length; i++) {
         queries[i] = new Query(i + 1, in);
      }
      Arrays.sort(queries, new Query.SortByFinish());
      int maxRoom = 0;
      int queriesDone = 0;
      for (Query q : queries) {
         int room = 0;
         for (int i = 1; i < rooms.length; i++) {
            if (rooms[i] <= q.start && (room == 0 || rooms[room] < rooms[i])) {
               room = i;
            }
         }
         if (room != 0) {
            q.room = room;
            rooms[room] = q.finish + 30;
            queriesDone++;
         }
         maxRoom = Math.max(maxRoom, room);
      }
      Arrays.sort(queries, new Query.SortById());
      out.println(queriesDone + " " + maxRoom);
      for (Query q : queries) {
         if (q.room != 0) {
            out.println(q.id + " " + q.room);
         }
      }
   }

   void run() {
      try {
         in = new Scanner(System.in);
         out = new PrintWriter(System.out);
      } catch (Exception e) {
         throw new Error(e);
      }
      try {
         solve();
      } finally {
         out.close();
      }
   }

   public static void main(String args[]) {
      new Main().run();
   }
}