C

import java.util.*;

class Dish {
    String name;
    int cost;
    int prestige;

    Dish(String name, int cost, int prestige) {
        this.name = name;
        this.cost = cost;
        this.prestige = prestige;
    }
}

public class problemC {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the budget and the number of recipes
        int budget = scanner.nextInt();
        int numRecipes = scanner.nextInt();

        // Skapa en lista för att lagra alla rätter
        List<Dish> dishes = new ArrayList<>();

        // Lägg till en grundrätt som alltid är tillgänglig
        dishes.add(new Dish("pizza_base", 0, 0));

        // Läs in recepten och skapa rätter från dem
        for (int i = 0; i < numRecipes; i++) {
            String derivedDishName = scanner.next();
            String baseDishName = scanner.next();
            String ingredient = scanner.next();
            int addedCost = scanner.nextInt();
            int addedPrestige = scanner.nextInt();

            // Hitta basrätten och dess kostnad
            int baseCost = 0;
            for (Dish dish : dishes) {
                if (dish.name.equals(baseDishName)) {
                    baseCost = dish.cost;
                    break;
                }
            }

            // Skapa den härledda rätten och lägg till den i listan
            Dish derivedDish = new Dish(derivedDishName, baseCost + addedCost, addedPrestige);
            dishes.add(derivedDish);
        }

        // Skapa en matris för dynamisk programmering med memoization
        int[][] dp = new int[budget + 1][dishes.size()];

        // Fyll i matrisen med dynamisk programmering
        for (int i = 0; i < dp[0].length; i++) {
            for (int j = 0; j <= budget; j++) {
                int cost = dishes.get(i).cost;
                int prestige = dishes.get(i).prestige;

                // Om rätten är dyrare än budgeten, använd värdet ovanför
                if (cost > j) {
                    dp[j][i] = (i > 0) ? dp[j][i - 1] : 0;
                } else {
                    // Annars beräkna det maximala prestigevärdet
                    int withoutThisDish = (i > 0) ? dp[j][i - 1] : 0;
                    int withThisDish = prestige + dp[j - cost][i];

                    dp[j][i] = Math.max(withoutThisDish, withThisDish);
                }
            }
        }

        // Hitta det maximala ackumulerade prestigevärdet och den minimala kumulativa kostnaden
        int maxPrestige = dp[budget][dishes.size() - 1];
        int minCost = budget;

        // Skapa en lista för att lagra de valda rätterna som bidrar till maximal prestiges
        List<Dish> selectedDishes = new ArrayList<>();

        // Återställ minCost till budget och spåra de valda rätterna
        for (int i = dishes.size() - 1; i >= 0; i--) {
            int cost = dishes.get(i).cost;
            if (maxPrestige - dishes.get(i).prestige >= 0 && dp[minCost][i] == maxPrestige - dishes.get(i).prestige) {
                selectedDishes.add(dishes.get(i));
                maxPrestige -= dishes.get(i).prestige;
                minCost -= cost;
            }
        }

        // Skriv ut resultatet
        System.out.println(maxPrestige);
        System.out.println(minCost);

        // Skriv ut de valda rätterna
        System.out.println("Selected Dishes:");
        for (Dish dish : selectedDishes) {
            System.out.println(dish.name);
        }

        scanner.close();
    }
}