Un grup de cercetatori pleaca într-o expeditie în
Oceanul Pacific. Dupa o furtuna puternica ramân fara apa. Desi se aflau
într-o situatie grea norocul vine pe neasteptate printr-o ploaie torentiala.
Toate vasele existente pe vapor sunt scoase si umplute cu apa. Fiecare vas în
care se retine apa de ploaie dispune de un dispozitiv care contorizeaza picaturile
de apa. Dupa ce se termina ploaia, apa strânsa este mutata în butoaiele
(toate goale) existente pe vapor.
Apa de ploaie s-a strâns în n vase. Dupa ploaie se stie ca fiecare
vas i contine un numar de xi picaturi (calculate de dispozitivele de contorizare),
1<=i <=n. Pe vas exista k butoaie, în fiecare butoi i se pot pune
vi picaturi, 1<=i<= k.
Cerinta
Sa se determine numarul maxim de butoaie care se pot umple.
Date de intrare
Fisierul de intrare pic.in
are urmatoarea structura:
- pe prima linie numarul n
- urmeaza n linii; pe cea de-a i-a linie dintre cele n se afla cifrele lui xi
precedate de numarul de cifre (toate separate între ele prin câte
un spatiu).
- pe linia n+2 se afla numarul k
- urmeaza k linii; cea de-a i-a linie dintre cele k contine cifrele lui vi precedate
de numarul de cifre (toate separate între ele prin câte un spatiu).
Date de iesire
Fisierul pic.out
va contine o linie pe care se afla numarul maxim de butoaie care se pot umple.
Restrictii
n -numar natural nenul <70
xi -numar natural nenul <1022, 1<=i<=n
k -numar natural nenul <40
vi-numar natural nenul <1022, 1<=i<=k
Exemple
pic.in
pic.out
4
1 5
2 1 0
2 2 0
1 7
3
2 3 0
3 4 0 0
2 1 1
2
prof. Doru Popescu Anastasiu
C.N. "Radu Greceanu" Slatina
Contact: dopopan at yahoo.com