Fişierul intrare/ieşire:	ambuscada.in, ambuscada.out	Sursă	Algoritmiada 2009, Runda Finala
Autor	Adrian Airinei	Adăugată de	Airinei Adrian •astronomy
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

Ambuscada

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?".

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 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.

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 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.

Restricţii

• 1 ≤ N, K, M, P ≤ 100 000
• 1 ≤ C_i, T_i, X_i ≤ 500 000
• 1 ≤ D_i ≤ 10¹²
• Datorita faptului ca soldatii au personalitate, nu exista doi soldati i si j diferiti pentru care C_i = C_j sau T_i = T_j.

Exemplu

Explicaţie

Nu poate cuceri niciun obiectiv intr-un timp de 1 minut deoarece are doar un singur soldat disponibil si trebuie sa trimita un grup format din exact 2 soldati in ambuscada. Poate trimite soldatii 1 si 2 pentru a cuceri obiectivul de dificultate 5 in 2 minute, respectiv soldatii 2 si 3 pentru a cuceri obiectivul de dificultate 6 in 3 minute.

Cum se trimit solutii?