| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Nakon par mjeseci zidanja kuća po Njemačkoj i puno zarađenog novca, Josip se vratio u Hrvatsku. Odmah prvu večer u Lijepoj Našoj odlučio je izvesti svoju prijateljicu Josipu na večeru. Kako obadvoje vole skupa jela i pića, Josip je čak $M$ puta tokom večeri odlazio do bankomata podignuti po $X_i$ kuna. Bankomat na kojem Josip podiže novce sadrži $N$ vrsta novčanica različitih vrijednosti pri čemu svake vrste ima neograničeno mnogo. Svaki put kada je Josip došao podići novce, na bankomatu je stajala obavijest: “Poštovani korisnici, zbog poteškoća u radu bankomata sve novčanice vrijednosti Ci neće imati ugodan miris, tj. smrdjet će. Hvala na razumijevanju!”
Jednom kada novčanice neke vrijednosti postanu smrdljive, zauvijek ostaju smrdljive.
Kako bi u restoranu izbjegao neugodne situacije sa smrdljivim novčanicama, Josip se pita može li bankomat isplatiti točno $X_i$ kuna bilo u jednoj ili u više manjih isplata koje u zbroju daju $X_i$ ali tako da bude siguran da neće dobiti smrdljivu novčanicu. Josip će od bankomata uvijek tražiti iznos koji je moguće isplatiti.
U prvom retku nalaze se prirodni brojevi $N$, $M$ ($1 ≤ M ≤ N ≤ 5000$), brojevi iz teksta zadatka.
U drugom retku nalazi se $N$ prirodnih brojeva $A_i$ ($1 ≤ A_i ≤ 10000$, $i=1 \dots N$) odvojenih razmakom, pri čemu je $A_1$ vrijednost novčanice prve vrste, $A_2$ vrijednost novčanice druge vrste i tako do $A_N$, vrijednosti novčanice $N$-te vrste.
U sljedećih $M$ redaka nalaze se po dva prirodna broja $X_i$ i $C_i$ ($1 ≤ X_i ≤ 10000$, $1 ≤ C_i ≤ 10000$, $i=1 \dots M$) odvojenih razmakom, pri čemu je $X_i$ iznos koji je Josip trebao podignuti u $i$-tom dolasku, a $C_i$ vrijednost novčanice koja je postala smrdljiva u $i$-tom dolasku.
U $i$-tom od $M$ redaka ispiši “DA” ako je Josip mogao isplatiti s bankomata $X_i$ kuna u $i$-tom dolasku bez da dobije neku smrdljivu novčanicu, inače ispiši “NE”.
4 2 2 5 6 1 11 6 11 1
DA NE
3 3 7 2 9 16 7 16 9 16 2
DA DA NE
5 3 5 2 10 7 6 13 5 12 10 11 7
NE DA NE
Opis prvog primjera: Kada prvi put Josip dođe na bankomat, on ne može zatražiti samo jednu isplatu od 11 kn jer mu npr. bankomat može dati novčanicu od 5 kn i smrdljivu novčanicu od 6 kn, ali može zatražiti tri isplate, jednu od 1 kn i dvije od 5 kn. Niti jednu od te tri isplate nije moguće izvršiti uz pomoć smrdljive novčanice, a ukupno je dobio željenih 11 kn. Drugi put kad Josip dođe na bankomat nije moguće isplatiti ukupno 11 kn bez da bude siguran da neće dobiti barem jednu smrdljivu novčanicu.