| Fişierul intrare/ieşire: | numerologie.in, numerologie.out | Sursă | Algoritmiada 2016 Runda 3 Seniori |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Numerologie
Eudanip este un nume cunoscut al concursurilor de informatică. Propunător prolific, consumator de mâncare fără sosuri sau legume, cel mai bun concurent dintre cei care nu ştiu să codeze. Dar probabil nu ştiţi că el are un frate, Namfosteubossdanip, care are o reputaţie comparabilă cu a fratelui său, doar că în lumea infractorilor.
Astăzi Namfosteubossdanip încearcă să strângă bani în faţă la AFI Cotroceni făcând scamatorii infantile. Aşezat între domnul care cântă la harpă şi domnii care joacă alba neagra, acesta vinde trecătorilor numere naturale la preţ ridicat. Nu înţelegem exact cum funcţionează afacerea lui Namfosteubossdanip, dar un lucru e sigur, dacă acesta vrea să poată produce numărul X, el trebuie neaparat să aibă în posesia sa cel puţin un factor prim al numărului X. Astfel, avându-l pe 7, spre exemplu, el poate produce şi vinde oricare din numerele 7, 14, 21.., în orice cantitate.
Namfosteubossdanip a primit o listă de comenzi de numere naturale pe care trebuie să le vândă. El doreşte să-şi cumpere numerele prime necesare pentru a onora aceste comenzi cheltuind cât mai puţin bani. Vi se dau N numere de valoare maxim M care trebuie vândute şi costul fiecărui număr prim mai mic sau egal cu M. Care este costul minim total necesar pentru ca Namfosteubossdanip să poată produce toate cele N numere din input?
Date de intrare
Fişierul de intrare numerologie.in va conţine pe prima sa linie numerele N, respectiv M. A doua linie conţine N numere naturale mai mici sau egale cu M şi mai mari sau egale cu 2. A treia linie conţine M valori. A i-a din aceste valori va fi egală cu costul numărului i, dacă acesta este prim. Dacă nu este prim, valoarea corespunzătoare va fi egală cu -1.
Date de ieşire
Fişierul de ieşire numerologie.out va contine un singur numar reprezentand costul minim de a acoperi toate cele N numere.
Restricţii
- 1 ≤ N ≤ 1250
- 2 ≤ M ≤ 1250
- Costurile numerelor prime vor fi numere naturale din intervalul [1..106]
- 30% din teste vor avea în plus N, M ≤ 60
Exemplu
| numerologie.in | numerologie.out |
|---|---|
| 3 10 8 6 5 -1 5 3 -1 3 -1 6 -1 -1 -1 | 8 |
Explicaţie
Suntem obligaţi să cumpărăm numerele prime 2 şi 5, iar acestea sunt şi suficiente.
