V obchode s úlohami pripravujú akciu, kúp 5 a 2 najlacnejšie dostaneš zadarmo. Alebo to malo byť kúp 8 a 3 dostaneš zadarmo? Problém je, že táto akcia sa stratila a nikto teraz nevie aké čísla tam boli. Vedúci prevádzky potrebuje teda vymyslieť aké čísla budú v akcii. Najprv by ale chcel vedieť, koľko najviac potom bude môcť stratiť na jednom nákupe.
Na vstupe dostanete zoznam cien produktov ktoré obchod predáva a niekoľko otázok v tvare $a b$, teda aká môže byť najväčšia cena vecí ktoré dostane zákazník zadarmo, ak bude akcia “Kúp $a$ a $b$ najlacnejších dostaneš zadarmo”. Každý predmet v obchode si môže zákazník kúpiť len raz.
V prvom riadku vstupu sú číslo $n$ a $q$ ($1 \leq n, q \leq 10^6$) udávajúce počet predmetov v obchode a počet otázok. V druhom riadku je $n$ medzerou oddelených čísel $c_i$ ($1 \leq c_i \leq 10^6$) udávajúce ceny predmetov. Nasleduje $q$ riadkov pri čom na $i$-tom sa nachádzajú medzerou oddelené čísla $a_i$ a $b_i$ ($1 \leq b_i \leq a_i \leq n$).
Vypíš $q$ riadkov, na $i$-tom z nich jedno celé číslo a to odpoveď na $i$-tu otázku.
5 3
5 3 1 5 2
3 2
1 1
5 3
8
5
6
V prvej otázke môžeme kúpiť predmety s cenou $5$, $3$ a $5$, dva najlacnejšie z nich stoja spolu $3+5=8$. V druhej otázke kupujeme len jeden predmet a je zadarmo, teda môžeme kúpiť predmet s cenou $5$. V poslednej otázke kupujeme všetky predmety a zadarmo sú tri najlacnejšie, teda $1+2+3=6$.