Module: Tris quadratiques

L'équipage du vaisseau interplanétaire Serenity de la classe Firefly livre des cargaisons sur différentes planètes du système stellaire. Le navire a une soute secrète composée de N × M cellules. Chaque cellule de la soute a un volume maximum qu'elle peut accueillir. Il est impossible d'emboîter dans la cellule une charge d'un volume supérieur au volume maximal de la cellule. Une seule charge exactement peut être placée dans une cellule. 

 

   Serenity Le capitaine Malcolm Reynolds réfléchit au placement de la cargaison dans les cellules. Aidez-le à déterminer la quantité maximale de cargaison que le capitaine peut livrer.

 

Entrée
La première ligne contient les nombres N et M (\(1 \leq N, M \leq 40\) ). Chacune des lignes N suivantes contient des nombres M indiquant le volume maximum de la cellule correspondante. La (N+2)ième ligne contient le nombre K (\(1 \leq K \leq 2000\)) – la quantité de fret. La (N+3)-ième ligne contient des nombres K, dont le i-ième est – volume iième cargaison. Tous les tomes – nombres naturels n'excédant pas 10⁹.

Mentions légales
Il est nécessaire d'afficher un numéro – la quantité maximale de fret pouvant être livrée.