$N$ vaches ($3 \le N \le 200$) font une fête du Nouvel An. Chacune cuisine plusieurs aliments, en unités appelées plats. $D$ types ($5 \le D \le 100$), numérotés $1..D$.

Le coordinateur des vaches maximise les plats, limitant chaque type. Une vache apporte $K$ plats ($1 \le K \le 5$), tous différents (pas3 tartes bovines, mais tarte, pain et luzerne à sauce orange). Quel maximum ?

Entrée

• Ligne $1$ : trois entiers $N$, $K$, $D$.
• Ligne $2$ : $D$ entiers non négatifs, limites totales de chaque type.
• Lignes $3..N+2$ : premier entier $Z$ ($1 \le Z \le D$), nombre de types préparables ; ensuite $Z$ identifiants, premier type d’abord, deuxième ensuite, etc.

Sortie

Une ligne, un entier : maximum de plats.

Exemples

Entrée 1

4 3 5
2 2 2 2 3
4 1 2 3 4
4 2 3 4 5
3 1 2 4
3 1 2 3

Sortie 1

9

Remarque

Explication de l’entrée

données — explication

• 4 3 5 — 4 vaches, chacune au plus3 plats,5 types.
• 2 2 2 2 3 — Types1–4 au plus2 chacun, type5 au plus3.
• 4 1 2 3 4 — Cette vache cuisine4 types :1, 2, 3, 4.
• 4 2 3 4 5 — Cuisine4 types :2, 3, 4, 5.
• 3 1 2 4 — Cuisine3 types :1, 2, 4.
• 3 1 2 3 — Cuisine3 types :1, 2, 3.

Explication de la sortie

[Vache1 apporte3, 4 ;2 apporte3, 4, 5 ;3 apporte1, 2 ;4 apporte1, 2.]

Auteur du problème : Hal Burch, 2001