← 返回题目列表

Codeforces · 1697/B

B. 促销

中文机器翻译题面 查看原题

商店出售 $$$n$$$ 商品,第 $$$i$$$ 商品的价格为 $$$p_i$$$。商店管理层将举办促销活动:如果顾客购买至少 $$$x$$$ 商品,则 $$$y$$$ 最便宜的商品免费。

管理层尚未决定 $$$x$$$ 和 $$$y$$$ 的确切值。因此,他们要求您处理 $$$q$$$ 查询:对于给定的 $$$x$$$ 和 $$$y$$$ 值,确定如果客户进行了一次购买,则免费收到的物品的最大总价值。

请注意,所有查询都是独立的;它们不会影响商店的库存。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)——分别是商店中的商品数量和查询数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^6$$$),其中 $$$p_i$$$ — 第 $$$i$$$ 商品的价格。

以下 $$$q$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le y_i \le x_i \le n$$$) — 第 $$$i$$$ 查询中参数 $$$x$$$ 和 $$$y$$$ 的值。

输出

对于每个查询,打印一个整数 - 一次购买免费收到的商品的最大总价值。

示例

输入 #1

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

输出 #1

8
5
6

注意

在第一个查询中,客户可以购买三件价值 $$$5, 3, 5$$$ 的商品,其中最便宜的两个是 $$$3 + 5 = 8$$$。

在第二个查询中,客户可以购买两件价值 $$$5$$$ 和 $$$5$$$ 的商品,其中最便宜的是 $$$5$$$。

在第三个查询中,顾客必须购买所有商品才能免费获得其中最便宜的三件商品;他们的总价是 $$$1 + 2 + 3 = 6$$$。