Fişierul intrare/ieşire:numerologie.in, numerologie.outSursăAlgoritmiada 2016 Runda 3 Seniori
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.innumerologie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?