| Fişierul intrare/ieşire: | tricouri.in, tricouri.out | Sursă | preONI 2007, Runda 2 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
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.in | tricouri.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.
