The store sells $n$ items, the price of the $i$-th item is $p_i$. The store's management is going to hold a promotion: if a customer purchases at least $x$ items, $y$ cheapest of them are free.

The management has not yet decided on the exact values of $x$ and $y$. Therefore, they ask you to process $q$ queries: for the given values of $x$ and $y$, determine the maximum total value of items received for free, if a customer makes one purchase.

Note that all queries are independent; they don't affect the store's stock.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of items in the store and the number of queries, respectively.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^6$), where $p_i$ — the price of the $i$-th item.

The following $q$ lines contain two integers $x_i$ and $y_i$ each ($1 \le y_i \le x_i \le n$) — the values of the parameters $x$ and $y$ in the $i$-th query.


-----Output-----

For each query, print a single integer — the maximum total value of items received for free for one purchase.


-----Examples-----

Input
5 3
5 3 1 5 2
3 2
1 1
5 3
Output
8
5
6


-----Note-----

In the first query, a customer can buy three items worth $5, 3, 5$, the two cheapest of them are $3 + 5 = 8$.

In the second query, a customer can buy two items worth $5$ and $5$, the cheapest of them is $5$.

In the third query, a customer has to buy all the items to receive the three cheapest of them for free; their total price is $1 + 2 + 3 = 6$.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
import sys
I = sys.stdin.readline
O = sys.stdout.write
(a, b) = map(int, I().split())
c = list(map(int, I().split()))
c.sort()
c = c[::-1]
for i in range(1, len(c)):
	c[i] = c[i] + c[i - 1]
for j in range(b):
	(p, r) = map(int, I().split())
	if p == r:
		O(str(c[p - 1]) + '\n')
	else:
		O(str(c[p - 1] - c[p - r - 1]) + '\n')


import math
import sys
import threading
input = sys.stdin.readline
from collections import defaultdict as dd
from collections import deque

def helper(nd):
	vis[nd] = 1
	here = 1
	for ng in gr[nd]:
		if vis[ng] == 0:
			here += helper(ng)
	tot[nd] = here
	return here

def helper1(nd, par):
	ch = []
	for ng in gr[nd]:
		if ng != par:
			ch.append(ng)
	if len(ch) == 0:
		return 0
	if len(ch) == 1:
		return tot[nd] - 2
	return max(tot[ch[1]] - 1 + helper1(ch[0], nd), tot[ch[0]] - 1 + helper1(ch[1], nd))

def shouvik():
	global vis, tot, gr, dp
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	pr = [arr[0]]
	for i in range(1, n):
		pr.append(pr[-1] + arr[i])
	while q:
		(x, y) = map(int, input().split())
		q -= 1
		idx1 = n - x
		idx2 = idx1 + y - 1
		if idx1 == 0:
			print(pr[idx2])
		else:
			print(pr[idx2] - pr[idx1 - 1])
shouvik()


import sys
input = sys.stdin.readline
print = sys.stdout.write
(n, q) = map(int, input().split())
items = list(map(int, input().split()))
items.sort(reverse=True)
prefix = [0] * (n + 1)
for i in range(n):
	prefix[i + 1] = items[i] + prefix[i]
for i in range(q):
	(x, y) = map(int, input().split())
	price = prefix[x] - prefix[x - y]
	print(str(price) + '\n')


r = open(0)
g = lambda : map(int, next(r).split())
(n, q) = g()
a = [0]
for x in sorted(g())[::-1]:
	a += (a[-1] + x,)
for b in [0] * q:
	(x, y) = g()
	print(a[x] - a[x - y])


f = open(0)
R = lambda : map(int, next(f).split())
(n, q) = R()
a = [0]
for x in sorted(R())[::-1]:
	a += (a[-1] + x,)
for _ in [0] * q:
	(x, y) = R()
	print(a[x] - a[x - y])


import sys
input = sys.stdin.readline
print = sys.stdout.write
(n, q) = map(int, input().split())
items = list(map(int, input().split()))
items.sort(reverse=True)
for idx in range(1, n):
	items[idx] = items[idx] + items[idx - 1]
for _ in range(q):
	(x, y) = map(int, input().split())
	if x == y:
		print(str(items[x - 1]) + '\n')
	else:
		print(str(items[x - 1] - items[x - y - 1]) + '\n')


def read_int() -> int:
	return int(input().strip())

def read_ints_map() -> map:
	return map(int, input().strip().split())

def read_ints_list() -> [int]:
	return [*read_ints_map()]
try:
	fin = open('./input.txt')
	import sys
	sys.stdin = fin
except:
	pass
f = open(0)
R = lambda : map(int, next(f).split())
(n, q) = R()
b = [0] * (n + 1)
for (i, p) in enumerate(sorted(R(), reverse=True)):
	b[i + 1] = b[i] + p
for _ in range(q):
	(x, y) = R()
	print(b[x] - b[x - y])


def read_int() -> int:
	return int(input().strip())

def read_ints_map() -> map:
	return map(int, input().strip().split())

def read_ints_list() -> [int]:
	return [*read_ints_map()]
try:
	FIN = open('./input.txt')
except:
	FIN = open(0)
R = lambda : map(int, next(FIN).split())
(n, q) = R()
b = [0] * (n + 1)
for (i, p) in enumerate(sorted(R(), reverse=True)):
	b[i + 1] = b[i] + p
for _ in range(q):
	(x, y) = R()
	print(b[x] - b[x - y])


import random
import io, os
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
p = [int(i) for i in input().split()]
p.sort(reverse=True)
sums = [0 for i in range(n)]
sums[0] = p[0]
for i in range(1, n):
	sums[i] = sums[i - 1] + p[i]
for i in range(q):
	(x, y) = map(int, input().split())
	if y == x:
		sys.stdout.write(str(sums[x - 1]) + '\n')
	else:
		sys.stdout.write(str(sums[x - 1] - sums[x - 1 - y]) + '\n')


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
for i in range(1, n):
	arr[i] += arr[i - 1]
arr = [0] + arr
for i in range(q):
	(x, y) = map(int, input().split())
	print(arr[n - x + y] - arr[n - x])


input = __import__('sys').stdin.readline
(n, m) = [int(a) for a in input().split()]
ar = list(map(int, input().split()))[:n]
ar.sort(reverse=True)
b = [ar[0]]
for i in range(1, n):
	b.append(b[-1] + ar[i])
for i in range(m):
	(x, y) = [int(a) for a in input().split()]
	if x == y:
		print(b[x - 1])
		continue
	print(b[x - 1] - b[x - y - 1])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
s = [0]
for i in range(n):
	s.append(p[i] + s[i])
for _ in range(q):
	(x, y) = map(int, input().split())
	print(s[n - x + y] - s[n - x])


import sys
input = sys.stdin.readline

def solve():
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	ps = [0] * (n + 1)
	curr = 0
	for i in range(n):
		curr += arr[i]
		ps[i + 1] = curr
	for _ in range(q):
		(x, y) = map(int, input().split())
		print(ps[n - x + y] - ps[n - x])
	return
solve()


from itertools import accumulate

def main():
	(n, q) = map(int, input().split())
	prices = list(map(int, input().split()))
	prices.sort()
	acc_prices = list(accumulate(prices, initial=0))
	for _ in range(q):
		(x, y) = map(int, input().split())
		ans = acc_prices[n - x + y] - acc_prices[n - x]
		print(ans)
import sys
input = sys.stdin.readline
exit(main())


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
brr = [0]
for i in range(n):
	brr.append(arr[i] + brr[i])
for _ in range(q):
	(x, y) = map(int, input().split())
	print(brr[n - x + y] - brr[n - x])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
x = 0
for i in range(n):
	a[i] += x
	x = a[i]
for i in range(q):
	(x, y) = map(int, input().split())
	ans = 0
	if x == y:
		ans = a[x - 1]
	else:
		ans = a[x - 1] - a[x - y - 1]
	sys.stdout.write(str(ans) + '\n')


import sys
input = sys.stdin.readline
(a, b) = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
x = [0]
for i in l:
	x.append(i + x[-1])
for _ in range(b):
	(y, z) = map(int, input().split())
	print(x[y] - x[y - z])


f = open(0)
R = lambda : map(int, next(f).split())
(n, q) = R()
b = [0]
for i in sorted(R()):
	b.append(b[-1] + i)
for i in range(q):
	(x, y) = R()
	print(b[n - x + y] - b[n - x])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
p = p[::-1]
res = []
ans = 0
for i in range(n):
	ans += p[i]
	res.append(ans)
for i in range(q):
	(x, y) = map(int, input().split())
	if x - y - 1 < 0:
		print(res[x - 1])
	else:
		print(res[x - 1] - res[x - y - 1])


import sys
input = sys.stdin.readline
(n, q) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = sorted(p)
prefix = [0]
for (i, _p) in enumerate(p):
	prefix.append(prefix[i] + _p)
for _ in range(q):
	(x, y) = [int(i) for i in input().split()]
	print(prefix[-(x - y + 1)] - prefix[-x - 1])


import sys
from itertools import accumulate

def rall():
	return [x.strip() for x in sys.stdin.readlines()]

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
(n, q) = map(int, rl().split(' '))
pvals = list(map(int, rl().split(' ')))
pvals.sort()
accum = [0, *accumulate(pvals)]
for _ in range(q):
	(x, y) = map(int, rl().split(' '))
	print(accum[n - x + y] - accum[n - x])


import sys
from itertools import accumulate
input = sys.stdin.readline
(n, q) = list(map(int, input().split()))
p = list(map(int, input().split()))
p.sort()
preSum = list(accumulate(p, initial=0))
for _ in range(q):
	(x, y) = list(map(int, input().split()))
	(l, r) = (n - x, n - x + y - 1)
	print(preSum[r + 1] - preSum[l])


import sys
(n, p) = map(int, sys.stdin.readline().split())
l = map(int, sys.stdin.readline().split())
l = sorted(l, reverse=True)
for i in range(n - 1, 0, -1):
	l[i - 1] += l[i]
for _ in range(p):
	(xi, yi) = map(int, sys.stdin.readline().split())
	a = n - xi
	b = a + yi
	if a == 0:
		print(l[-b])
	else:
		print(l[-b] - l[-a])


import sys
ipt = sys.stdin.readline
(n, t) = map(int, ipt().split())
arr = list(map(int, ipt().split()))
arr.sort()
arr1 = []
o = 2
arr1.append(0)
arr1.append(arr[n - 1])
s = n - 2
while s >= 0:
	arr1.append(arr1.__getitem__(o - 1) + arr[s])
	o += 1
	s -= 1
for e in range(t):
	(x, y) = map(int, ipt().split())
	print(arr1[n - (n - x)] - arr1[x - y])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
s = [a[0]]
for i in range(1, n):
	s.append(a[i] + s[i - 1])
for i in range(q):
	(x, y) = map(int, input().split())
	l = n - x
	r = l + y - 1
	if l == 0:
		print(s[r])
	else:
		print(s[r] - s[l - 1])


f = open(0)
R = lambda : map(int, next(f).split())
(n, q) = R()
b = [0]
a = sorted(R(), reverse=True)
for i in a:
	b.append(b[-1] + i)
for _ in [0] * q:
	(x, y) = R()
	print(b[x] - b[x - y])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = [0]
for i in range(n):
	b.append(a[i] + b[i])
for i in range(q):
	(x, y) = map(int, input().split())
	print(b[n - x + y] - b[n - x])


inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
strlst = lambda : list(input())
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10
(n, q) = mul()
a = lst()
a.sort(reverse=True)
l = [0] * n
cnt = 0
for i in range(n):
	cnt += a[i]
	l[i] = cnt
for i in range(q):
	(x, y) = mul()
	d = x - y
	if d == 0:
		ans = l[x - 1]
	else:
		ans = l[x - 1] - l[d - 1]
	print(ans)


import io, os, sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
cp = p.copy()
for i in range(1, n):
	cp[i] = cp[i] + cp[i - 1]
cp = [0] + cp
for _ in range(q):
	(x, y) = map(int, input().split())
	print(cp[n] - cp[n - x] - (cp[n] - cp[n - x + y]))


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = sorted([*map(int, input().split())], reverse=True)
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
	dp[i] = dp[i - 1] + arr[i]
for i in range(q):
	(x, y) = map(int, input().split())
	if x == y:
		print(dp[x - 1])
	else:
		print(dp[x - 1] - dp[x - y - 1])


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = 1
for i in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	pre = [0]
	for i in range(n):
		pre.append(pre[-1] + arr[i])
	for i in range(q):
		(x, y) = map(int, input().split())
		print(pre[n - x + y] - pre[n - x])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
aa = [0 for i in range(n + 1)]
aa[-2] = a[-1]
for i in range(n - 1):
	aa[-i - 3] = aa[-i - 2] + a[-i - 2]
for _ in range(q):
	(x, y) = map(int, input().split())
	print(aa[n - x] - aa[n - x + y])


import sys
input = sys.stdin.readline

def nextInt():
	return int(input())

def arrayIn():
	return list(map(int, input().split()))

def nextLine():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, Q) = invr()
arr = arrayIn()
suffix = [0] * (n + 1)
arr.sort()
for i in range(n):
	suffix[i + 1] = suffix[i] + arr[n - i - 1]
for q in range(Q):
	(x, y) = invr()
	print(suffix[x] - suffix[x - y])


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
prr = [0] * (n + 1)
for i in range(n):
	prr[i + 1] = prr[i] + arr[i]
for i in range(q):
	(x, y) = map(int, input().split())
	print(prr[x] - prr[x - y])


class Solution:

	def Promo(self, n, pref, x, y):
		return pref[n - x + y] - pref[n - x]
import sys
input = sys.stdin.readline
sol = Solution()
(n, q) = list(map(int, input().split()))
pi = list(map(int, input().split()))
pi.sort()
pref = [0]
summ = 0
for i in range(n):
	summ += pi[i]
	pref.append(summ)
for _ in range(q):
	(x, y) = list(map(int, input().split()))
	print(sol.Promo(n, pref, x, y))


import collections
import math

def function():
	(n, q) = map(int, input().split(' '))
	a = [0]
	res = []
	for x in sorted([int(e) for e in input().split()])[::-1]:
		a += (a[-1] + x,)
	for _ in [0] * q:
		(x, y) = map(int, input().split(' '))
		res.append(a[x] - a[x - y])
	return res
res = function()
for e in res:
	print(e)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
(n, q) = get_ints()
arr = get_list()
arr.sort()
pre = [arr[0] for _ in range(n)]
for i in range(1, n):
	pre[i] = pre[i - 1] + arr[i]
for _ in range(q):
	(x, y) = get_ints()
	if x == n:
		if y != 0:
			print(pre[y - 1])
		else:
			print(0)
	else:
		ind = n - x - 1
		off = pre[ind + y] - pre[ind]
		print(off)


import sys
input = lambda : sys.stdin.readline().strip()
d = [0]
(a, b) = map(int, input().split())
l = sorted(list(map(int, input().split())), reverse=True)
s = 0
v = 0
for i in l:
	v += i
	d.append(v)
for _ in range(b):
	(n, m) = map(int, input().split())
	print(d[n] - d[n - m])


import sys
import collections
import bisect
import math
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)
(n, q) = list(map(int, sys.stdin.readline().split()))
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
prefix = [0]
curr = 0
for num in arr:
	curr += num
	prefix.append(curr)
for _ in range(q):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	i = len(prefix) - x - 1
	j = i + y
	print(prefix[j] - prefix[i])


import sys
(n, q) = map(int, sys.stdin.readline().split())
lst = list(map(int, sys.stdin.readline().split()))
lst.sort(reverse=True)
pre = [lst[0]]
for j in range(1, n):
	pre.append(pre[-1] + lst[j])
for j in range(q):
	(x, y) = map(int, sys.stdin.readline().split())
	a = pre[x - 1]
	ele = x - y
	if ele == 0:
		print(a)
	else:
		b = pre[ele - 1]
		print(a - b)


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
from itertools import accumulate
import sys
from bisect import *
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline

def solve():
	(n, q) = [int(x) for x in input().split(' ')]
	p = [int(x) for x in input().split(' ')]
	p.sort(reverse=True)
	qs = []
	for _ in range(q):
		(x, y) = [int(x) for x in input().split(' ')]
		qs.append([x, y])
	pfs = list(accumulate(p))
	for (x, y) in qs:
		if x == y:
			total = pfs[x - 1]
		else:
			total = pfs[x - 1] - pfs[x - y - 1]
		print(total)
solve()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, q) = mp()
l = li()
l.sort()
l.reverse()
k = [l[0]]
s = l[0]
for i in range(1, n):
	s += l[i]
	k.append(s)
for _ in range(q):
	(s, s1) = (0, 0)
	(x, y) = mp()
	if x - y == 0:
		print(k[x - 1])
	else:
		print(k[x - 1] - k[x - y - 1])


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)
ans = [0]
item = []
for i in l:
	ans.append(ans[-1] + i)
for i in range(m):
	(x, y) = map(int, input().split())
	item.append(ans[n - x + y] - ans[n - x])
for i in item:
	print(i)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)
ans = [0]
c = []
for i in l:
	ans.append(ans[-1] + i)
for i in range(m):
	(x, y) = map(int, input().split())
	if x != y:
		c.append(ans[x] - ans[x - y])
	else:
		c.append(ans[x])
for i in c:
	print(i)


from collections import Counter
import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def solve(A, i, j):
	if i == j:
		return A[i - 1]
	else:
		return A[i - 1] - A[i - j - 1]
(n, m) = get_ints()
arr = get_ints()
arr.sort(reverse=True)
for i in range(1, len(arr)):
	arr[i] = arr[i] + arr[i - 1]
for i in range(m):
	(i, j) = get_ints()
	print(solve(arr, i, j))


from collections import deque, defaultdict, Counter, OrderedDict
from itertools import product, groupby, permutations, combinations, accumulate, zip_longest, combinations_with_replacement
from math import gcd, floor, inf, log2, sqrt, log10, factorial
from bisect import bisect_right, bisect_left, insort_left
from statistics import mode
from string import ascii_lowercase, ascii_uppercase
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, nlargest, nsmallest, merge
from copy import deepcopy
from random import shuffle, randint
import random
from operator import xor, or_
from typing import List
(n, cases) = map(int, input().split())
arr = sorted(map(int, input().split()))[::-1]
pre = [0] + list(accumulate(arr))
ans = []
for _ in range(cases):
	(x, y) = map(int, input().split())
	ans.append(pre[x] - pre[x - y])
for n in ans:
	print(n)


import sys
input = sys.stdin.readline

def free(price, n, x, y):
	if x == n:
		return price[y - 1]
	return price[n - x + y - 1] - price[n - x - 1]
(n, queries) = map(int, input().split())
price = list(map(int, input().split()))
price = sorted(price)
for i in range(1, n):
	price[i] += price[i - 1]
for _ in range(queries):
	(x, y) = map(int, input().split())
	print(free(price, n, x, y))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [0] + [int(i) for i in input().split()]
a.sort()
for i in range(1, len(a)):
	a[i] += a[i - 1]
for _ in range(m):
	(x, y) = map(int, input().split())
	print(a[n - x + y] - a[n - x])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
p = list(map(int, input().split()))
p = sorted(p, reverse=True)
s = [p[0]]
for i in range(1, n):
	s.append(s[-1] + p[i])
for _ in range(q):
	(x, y) = map(int, input().split())
	if y == 0:
		print(0)
	elif x - y == 0:
		print(s[x - 1])
	else:
		print(s[x - 1] - s[x - y - 1])


from os import error
import sys
input = sys.stdin.readline
DEBUG = False

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve(sms):
	(n, m) = inlt()
	if n == m:
		return sms[n - 1]
	return sms[n - 1] - sms[n - m - 1]
(n, q) = inlt()
datum = sorted(inlt())[::-1]
sms = [0] * n
for i in range(n):
	sms[i] = datum[i]
	if i > 0:
		sms[i] += sms[i - 1]
for t in range(q):
	ans = solve(sms)
	print(ans)


(n, q) = map(int, input().split())
p = list(map(int, input().split()))
pr = [0] * (len(p) + 1)
a = []
p.sort(reverse=True)
for i in range(1, len(pr)):
	pr[i] = pr[i - 1] + p[i - 1]
for i in range(q):
	(x, y) = map(int, input().split())
	s = pr[x] - pr[x - y]
	a.append(s)
for i in range(len(a)):
	print(a[i])


from collections import Counter
from functools import lru_cache
import heapq
from itertools import combinations
import sys
input = sys.stdin.readline
(n, x) = map(int, input().split())
array = list(map(int, input().split()))
queries = []
for z in range(x):
	queries.append(list(map(int, input().split())))

def solve():
	result = []
	array.sort(reverse=True)
	prefixSum = []
	currentSum = 0
	for num in array:
		currentSum += num
		prefixSum.append(currentSum)
	for (left, right) in queries:
		diff = left - right
		leftSum = 0 if not diff else prefixSum[diff - 1]
		result.append(prefixSum[left - 1] - leftSum)
	return result
res = solve()
for re in res:
	print(re)


(n, q) = map(int, input().split())
array = sorted(list(map(int, input().split())), reverse=True)
sums = [0]
for i in range(n):
	sums.append(sums[-1] + array[i])
results = []
for i in range(q):
	(x, y) = map(int, input().split())
	results.append(sums[x] - sums[x - y])
print(*results, sep='\n')


(n, q) = [int(v) for v in input().split()]
p = [int(v) for v in input().split()]
p = sorted(p, reverse=True)
result = []
for i in range(1, len(p)):
	p[i] = p[i] + p[i - 1]
for _ in [0] * q:
	(x, y) = [int(v) for v in input().split()]
	result.append(p[x - 1] - (p[x - y - 1] if x != y else 0))
for v in result:
	print(v)


import sys
from itertools import accumulate
sys.setrecursionlimit(2 * 10 ** 6)

def test():
	pass

def main():
	(n, q) = map(int, input().split())
	ps = list(map(int, input().split()))
	qs = []
	for _ in range(q):
		qs.append(list(map(int, input().split())))
	ps.sort()
	ps = ps[::-1]
	acc = [0] + list(accumulate(ps))
	for (x, y) in qs:
		a = x - y
		print(acc[x] - acc[a])

def init():
	import sys
	import os
	if 'DOCKER_HOST' in os.environ:
		test()
		sys.stdin = open('test.txt')
init()
main()


(n, q) = map(int, input().split())
l = []
l = map(int, input().split())
l = list(l)
X = []
Y = []
for i in range(0, q):
	(x, y) = map(int, input().split())
	X.append(x)
	Y.append(y)
m = len(l)
x1 = len(X)
y1 = len(Y)
l.sort()
sum = [0]
for i in range(0, m):
	sum.append(sum[i] + l[i])
for j in range(0, x1):
	s = sum[m - X[j] + Y[j]] - sum[m - X[j]]
	print(s)


import sys
buffer = sys.stdin.readlines()
(n, q) = list(map(int, buffer[0].split()))
array = list(map(int, buffer[1].split()))
array.sort()
prefix = [0] * (n + 1)
for i in range(1, n + 1):
	prefix[i] = prefix[i - 1] + array[i - 1]
ans = ''
for j in range(q):
	(x, y) = [int(elem) for elem in buffer[2 + j].split()]
	res = prefix[n - x + y] - prefix[n - x]
	ans += str(res) + '\n'
sys.stdout.write(ans)


(n, q) = [int(x) for x in input().split()]
elements = [int(x) for x in input().split()]
queries = []
for i in range(q):
	xy = [int(x) for x in input().split()]
	queries += xy
elements.sort(reverse=True)
for i in range(1, int(n)):
	elements[i] += elements[i - 1]
for i in range(0, len(queries), 2):
	x = queries[i]
	y = queries[i + 1]
	if x == y:
		print(elements[x - 1])
	else:
		print(elements[x - 1] - elements[x - y - 1])


from re import L
res = []

def promo(nums, n, x, y):
	r = n - x
	if x == y:
		total = nums[x - 1]
	else:
		total = nums[x - 1] - nums[x - y - 1]
	res.append(total)
	return
(n, q) = input().split()
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(1, int(n)):
	A[i] += A[i - 1]
for i in range(int(q)):
	(x, y) = input().split()
	promo(A, int(n), int(x), int(y))
for n in res:
	print(n)


import sys
ipt = sys.stdin.readline
(n, q) = list(map(int, ipt().split()))
l = sorted(list(map(int, ipt().split())))
p = [0] * (n + 1)
for (i, elem) in enumerate(l):
	p[i + 1] = p[i] + l[i]
for _ in range(q):
	(x, y) = list(map(int, ipt().split()))
	print(p[-x + y - 1] - p[-x - 1])


(length, n) = map(int, input().split())
goods_prices = [int(s) for s in input().split()]
goods_prices.sort()
answer = []
answer_array = [0]
for i in range(length):
	answer_array.append(goods_prices[i] + answer_array[i])
for i in range(n):
	(last_indexes, cheap_prices) = map(int, input().split())
	answer.append(answer_array[length - last_indexes + cheap_prices] - answer_array[length - last_indexes])
for i in range(n):
	print(answer[i])


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
queries = []
for i in range(q):
	(x, y) = map(int, input().split())
	queries.append([x, y])
arr.sort(reverse=True)
sumarr = [0] * (n + 1)
sum1 = 0
for i in range(1, len(arr) + 1):
	sumarr[i] = arr[i - 1] + sumarr[i - 1]
for i in queries:
	elementstobechosen = i[0]
	elementstobediscounted = i[1]
	print(sumarr[elementstobechosen] - sumarr[elementstobechosen - elementstobediscounted])


(n, m) = list(map(int, input().split()))
l = list(map(int, input().split()))
q = []
for _ in range(m):
	q.append(list(map(int, input().split())))
l.sort()
prefix = [0]
for i in l:
	prefix.append(prefix[-1] + i)
for (i, j) in q:
	left = n - i
	print(prefix[left + j] - prefix[left])


import sys
input = sys.stdin.readline

def to_int(x):
	return int(float(x))
n_q_str = input().split()
p_str = input().split()
(n, q) = list(map(to_int, n_q_str))
p_list = list(map(to_int, p_str))
p_sorted = sorted(p_list, reverse=True)
prefix_list = []
s = 0
for a in range(n):
	s = s + p_sorted[a]
	prefix_list.append(s)
for b in range(q):
	x_y_str = input().split()
	(x, y) = list(map(to_int, x_y_str))
	if x == y:
		y_sum = prefix_list[x - 1]
	else:
		y_sum = prefix_list[x - 1] - prefix_list[x - y - 1]
	print(y_sum)