using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine().Split(' ').ToArray()[1]);
        List<Task> tasks = new List<Task>();
        int maxDeadline = 0;
        for (int i = 0; i < n; i++)
        {
            int[] given = Console.ReadLine().Split(new string[] { " - " }, StringSplitOptions.RemoveEmptyEntries)
                .Select(int.Parse).ToArray();
            int value = given[0];
            int deadline = given[1];
            if (maxDeadline < deadline)
            {
                maxDeadline = deadline;
            }
            tasks.Add(new Task(i + 1, value, deadline));
        }
        tasks.Sort();
        int totalValue = 0;
        List<Task> executed = new List<Task>();
        foreach (var task in tasks)
        {
            if (maxDeadline > executed.Count)
            {
                totalValue += task.Value;
                executed.Add(task);
            }
        }
        executed = executed.OrderBy(task => task.Deadline).ToList();
        Console.WriteLine("Optimal schedule: " + string.Join(" -> ", executed));
        Console.WriteLine("Total value: " + totalValue);
    }

    class Task : IComparable<Task>
    {
        public int TaskNum { get; }
        public int Value { get; }
        public int Deadline { get; }

        public Task(int taskNum, int value, int deadline)
        {
            this.TaskNum = taskNum;
            this.Value = value;
            this.Deadline = deadline;
        }
        public int CompareTo(Task other)
        {
            int cmp = other.Value.CompareTo(this.Value);
            if (cmp == 0)
                cmp = other.Deadline.CompareTo(this.Deadline);

            return cmp;
        }

        public override string ToString()
        {
            return TaskNum.ToString();
        }
    }
}