3. Akosi sa stratila

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.

Úloha

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.

Formát vstupu

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

Formát výstupu

Vypíš \(q\) riadkov, na \(i\)-tom z nich jedno celé číslo a to odpoveď na \(i\)-tu otázku.

Príklad

Input:

5 3
5 3 1 5 2
3 2
1 1
5 3

Output:

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