Fişierul intrare/ieşire:tricouri.in, tricouri.outSursăpreONI 2007, Runda 2
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.3 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Tricouri

Gigel are N tricouri, fiecare tricou avand inscriptionat ca model un numar cunoscut de buline. Ionel, uitandu-se un pic la tricouri, il roaga pe Gigel sa selecteze un numar de K tricouri din cele N care sa aibe in total un numar de buline divizibil cu P. Gigel, pretentios din fire, ii alege acele tricouri care au inscriptionate in total un numar maxim de buline si au si proprietatea ceruta.
Pentru M cerinte ale lui Ionel de forma precizata mai sus, sa se determine care este numarul maxim de buline divizibil la P, in urma alegerii a exact K tricouri. 

Date de intrare

Pe prima linie a fisierului de intrare tricouri.in se vor afla numerele N si M, numarul de tricouri, respectiv numarul de cerinte ale lui Ionel. Pe a doua linie urmeaza N numere naturale nenule, separate de cate un spatiu, reprezentand numarul de buline de pe fiecare tricou. Urmatoarele M linii pana la sfarsitul fisierului contin perechi de forma (K, P), reprezentand o cerinta a lui Ionel.

Date de iesire

Pentru fiecare cerinta de forma (K, P) a lui Ionel din fisierul de intrare se va afisa in fisierul de iesire tricouri.out numarul maxim de buline obtinute prin alegerea a exact K tricouri din cele N, numar care in plus sa fie divizibil la P. Daca nu exista nici o alegere posibila, pe linia corespunzatoare se va afisa -1.

Restrictii

  • 3 ≤ N ≤ 300 000
  • 3 ≤ M ≤ 100
  • Pentru fiecare cerinta a lui Ionel, 1 ≤ K ≤ 5 si 2 ≤ P ≤ 20
  • Numarul de buline de pe fiecare tricou este un numar natural cuprins intre 1 si 1 000 000

Exemplu

tricouri.intricouri.out
7 3
5 7 3 4 1 4 8
3 5
1 10
2 4
20
-1
12

Explicatie

Pentru prima cerinta, Gigel va alege tricourile cu 5, 7 si 8 buline, obtinand un numar de 20 de buline, care se divide cu 5. Nu exista alta posibilitate de a alege exact 3 tricouri care sa aiba in total un numar de buline divizibil cu 5 si mai mare de 20. Pentru a doua cerinta nu exista solutie (nu exista nici un tricou care sa aiba un numar de buline divizibil cu 10). Pentru ultima cerinta, Gigel va alege tricourile cu 5 si 7 buline, sau tricourile cu 4 si 8 buline, in ambele cazuri obtinand in total 12 buline.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content