Prologin
2024
Énoncé¶
Joseph Marchand aime bien diversifier ses recettes de crêpes, en utilisant des ingrédients plus ou moins élaborés. Cependant, une crêpe contenant des ingrédients trop originaux ne va pas nécessairement plaire aux clients, de même pour une crêpe trop basique. On définit la complexité d'une crêpe comme étant la somme de la complexité de chacun de ses ingrédients.
Après plusieurs retours, Joseph a réussi à déterminer un seuil maximal $K$ de complexité. Plus l'indice de complexité d'une crêpe est proche de ce seuil plus le client sera satisfait, mais Joseph doit être prudent de ne l'atteindre, ou pire encore de le dépasser, auquel cas le client ne sera pas convaincu face à la complexité de la crêpe.
Pour chaque étape d'une recette, Joseph possède à sa disposition différents ingrédients et doit en choisir un seul par étape. Joseph aimerait donc choisir les ingrédients d'une crêpe, de façon à maximiser l'indice de complexité tel qu'il soit strictement inférieur à $K$. En tant que nouvel employé de la crêperie, vous êtes chargé d'aider Joseph Marchand dans sa démarche.
Entrée¶
La première ligne contient deux entiers $N$ et $K$, où $N$ est le nombre d'étapes de la recette que prépare Joseph et $K$ le seuil maximal de complexité.
Les $N$ * 2 prochaines lignes correspondent chacune à une étape de la recette et sont organisées de la manière suivante : la première ligne contient un entier $M$ correspondant au nombre d'ingrédients disponibles pour cette étape. La seconde contient $M$ entiers indiquant pour chaque ingrédient son degré de complexité $K_i$ ($0 \lt K_i \le K$).
Sortie¶
Un unique entier représentant la complexité maximale que Joseph peut atteindre pour cette crêpe, ou -1 s'il est impossible de ne pas atteindre ou dépasser $K$.
Contraintes¶
- $1 \le N \le 5$
- $1 \le K \le 50$
- $1 \le M \le 5$
Contraintes de performance¶
- $1 \le N \le 20$
- $1 \le K \le 200$
- $1 \le M \le 20$