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();
}
}