Promo (Codeforces 1697B)
Tags: Greedy, sortings

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.

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$$$.

Sample Inputs:
5 3
5 3 1 5 2
3 2
1 1
5 3

Sample Outputs:
8
5
6

Solution (Python):
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])

Solution (Python):
c = open(0)
W = lambda : map(int, next(c).split())
(t, x) = W()
l = [0]
for r in sorted(W())[::-1]:
    l += (l[-1] + r,)
for _ in [0] * x:
    (r, y) = W()
    print(l[r] - l[r - y])

Solution (Python):
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])