== include(page="template/taskheader" task_id="ambuscada") ==
Generalul sef Andrei are la dispozitie o armata formata din $N$ soldati si planuieste o ambuscada in veederea cuceririi unor obiective strategice. Pentru fiecare soldat se cunosc $C{~i~}$, capacitatea de efort a acestuia si $T{~i~}$, timpul exprimat in minute in care un soldat isi poate folosi toata capacitatea de efort. Andrei a primit de la superiorii sai o lista cu $P$ obiective, pentru fiecare obiectiv cunoscandu-se $D{~i~}$, gradul de dificultate care il presupune atacarea lui. Generalul Andrei a primit de asemenea si alte indicatii precise. El poate trimite in ambuscada un grup format din exact $K$ soldati. Un grup de soldati poate cuceri un obiectiv daca suma capacitatilor de efort a soldatilor este mai mare sau egala cu gradul de dificultate al obiectivului. Deoarece o data ce si-a utilizat capacitatea de efort un soldat este prea obosit pentru a mai efectua alte actiuni, timpul in care un grup de soldati cucereste un obiectiv reprezinta timpul maxim in care un soldat din grup isi foloseste capacitatea de efort. Acestea fiind spuse, Andrei va roaga sa ii raspundeti la $M$ intrebari primite de la comandantul sef. Comandantul sef i-a pus $M$ intrebari, a $i$-a intrebare fiind de tipul "care este dificultatea cea mai ridicata a unui obiectiv care se poate cuceri in cel mult $X{~i~}$ minute?".
Generalul sef Andrei are la dispozitie o armata formata din $N$ soldati si planuieste o ambuscada in vederea cuceririi unor obiective strategice. Pentru fiecare soldat se cunosc $C{~i~}$, capacitatea de efort a acestuia si $T{~i~}$, timpul exprimat in minute in care un soldat isi poate folosi toata capacitatea de efort. Andrei a primit de la superiorii sai o lista cu $P$ obiective, pentru fiecare obiectiv cunoscandu-se $D{~i~}$, gradul de dificultate care il presupune atacarea lui. Generalul Andrei a primit de asemenea si alte indicatii precise. El poate trimite in ambuscada un grup format din exact $K$ soldati. Un grup de soldati poate cuceri un obiectiv daca suma capacitatilor de efort a soldatilor este mai mare sau egala cu gradul de dificultate al obiectivului. Deoarece o data ce si-a utilizat capacitatea de efort un soldat este prea obosit pentru a mai efectua alte actiuni, timpul in care un grup de soldati cucereste un obiectiv reprezinta timpul maxim in care un soldat din grup isi foloseste capacitatea de efort. Acestea fiind spuse, Andrei va roaga sa ii raspundeti la $M$ intrebari primite de la comandantul sef. Comandantul sef i-a pus $M$ intrebari, a $i$-a intrebare fiind de tipul "care este dificultatea cea mai ridicata a unui obiectiv care se poate cuceri in cel mult $X{~i~}$ minute?".
h2. Date de intrare
Fişierul de intrare $ambuscada.in$ contine pe prima linie patru numere naturale, $N K M$ si $P$, avand semnificatia din enunt. Pe urmatoarele $N$ linii se afla cate doua numere naturale, $C{~i~}$ si $D{~i~}$, avand semnificatia din enunt. Pe cea de-a $N+2$-a linie se afla $P$ numere naturale reprezentand gradele de dificultate ale obiectivelor. Urmeaza apoi $M$ linii, pe fiecare linie aflandu-se cate un numar natural $X{~i~}$, reprezentand intrebarile puse de comandantul sef.
Fişierul de intrare $ambuscada.in$ contine pe prima linie patru numere naturale, $N K M$ si $P$, avand semnificatia din enunt. Pe urmatoarele $N$ linii se afla cate doua numere naturale, $C{~i~}$ si $T{~i~}$, avand semnificatia din enunt. Pe cea de-a $N+2$-a linie se afla $P$ numere naturale reprezentand gradele de dificultate ale obiectivelor. Urmeaza apoi $M$ linii, pe fiecare linie aflandu-se cate un numar natural $X{~i~}$, reprezentand intrebarile puse de comandantul sef.
h2. Date de ieşire
În fişierul de ieşire $ambuscada.out$ se vor afla $M$ linii, pe fiecare linie aflandu-se raspunsul la cate o intrebare pusa de comandant. Daca nu exista niciun obiectiv care sa poata fi cucerit, se va afisa $-1$, altfel se va afisa dificultatea maxima a unui obiectiv care poate fi cucerit.
În fişierul de ieşire $ambuscada.out$ se vor afla $M$ linii, pe fiecare linie aflandu-se raspunsul la cate o intrebare pusa de comandant. Daca nu exista niciun obiectiv care sa poata fi cucerit de un grup format din exact $K$ soldati, se va afisa $-1$, altfel se va afisa dificultatea maxima a unui obiectiv care poate fi cucerit.
h2. Restricţii
