HONI 2022./2023. 1. kolo 4. zadatak

Mala Lana i mali Fran su u posjeti tvornici čokolade. Vidjeli su kako se čokolada radi, degustirali je, a sada žele nekoliko i kupiti.

U dućanu postoji n vrsta čokolada, svaka od njih ima svoju cijenu ci. Mala Lana i mali Fran žele kupiti m čokolada. Mali je Fran smislio sljedeći način kako će podijeliti trošak u dućanu:

• Ako je čokolada jeftinija od k kuna, mala Lana će je platiti u cijelosti.
• Inače, mala Lana će dati k kuna, a mali Fran ostatak, tj. ci − k kuna.

Označimo s l koliko je kuna mala Lana potrošila na kupnju, a s f koliko je kuna mali Fran potrošio na kupnju. Mala Lana, nezadovoljna dogovorom, želi napakostiti Franu te odabrati čokolade takve da je izraz l − f što manji. Budući da je Fran neodlučan i ne zna još koliko čokolada želi kupiti, malu Lanu zanima minimalna vrijednost izraza l − f za q različitih brojeva ki i mi.

Pomozite joj u biranju čokolada i odredite minimalnu vrijednost izraza l − f za svaki od q upita.

Ulazni podaci

U prvom retku su prirodni brojevi n i q (1 ≤ n, q ≤ 10^5), broj čokolada i broj upita.

U drugom retku je niz od n prirodnih brojeva c1, c2, . . . , cq (1 ≤ ci ≤ 10^9), koji označavaju redom cijenu i-te čokolade.

U sljedećih q redaka su parovi prirodnih brojeva ki i mi (1 ≤ ki ≤ 10^9, 1 ≤ mi ≤ n), Franova granica plaćanja i broj čokolada koje će kupiti.

Izlazni podaci

U i-tom od q redaka ispišite odgovor na i-ti Lanin upit.

Bodovanje

Probni primjeri

Ulaz

5 2
1 9 22 10 19
18 4
5 2

Izlaz

34
-21

Pojašnjenje prvog probnog primjera:

U prvom slučaju mala Lana može uzeti čokolade sa cijenama 1, 9, 22 i 10. Mala Lana će platiti 38 kuna, a mali Fran 4. Tražena vrijednost je 38 − 4 = 34.

U drugom slučaju mala Lana će uzeti čokolade sa cijenama 22 i 19. Za njih će platiti 10 kuna, dok će mali Fran platiti 31 kunu. Tražena vrijednost je 10 − 31 = −21.

Ulaz

7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5

Izlaz

4
16
7
1

Ulaz

3 3
5 6 7
10 1
5 3
3 3

Izlaz

5
12
0