Promo

题意翻译

## 题目描述 一个商店正在出售 $ n $ 个物品，其中第 $ i $ 个物品价格为 $ p_i $ 。这个公司的老板想要进行一个优惠：如果一个客人购买了至少 $ x $ i个物品，其中最便宜的 $ 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 $ 的大小。 ## 输出格式 对于每种情况，输出一个整数，代表在这种情况下顾客最多可以~~白嫖~~省下的钱。 ## 样例解释 在第一种情况中，这个顾客可以购买三个价值为 $ 5, 3, 5$ 的物品，其中两个最便宜的价值为 $ 3 + 5 = 8 $ 。 在第二种情况中，这个顾客可以购买两个物品，价值为 $ 5 $ 和 $ 5 $ , 其中最便宜的为 $ 5 $ 。 在第三种情况中，这个顾客得购买所有物品来省下最便宜三个物品的钱： $ 1 + 2 + 3 = 6 $ 。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

8
5
6

说明

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

题目大意：
一个商店有 $ n $ 个物品，每个物品有各自的价格 $ p_i $。商店计划进行一个优惠活动：如果顾客购买至少 $ x $ 个物品，则其中最便宜的 $ y $ 个物品免费。你需要处理 $ q $ 个询问，对于每个给定的 $ x $ 和 $ y $，计算顾客在一次购买中最多能免费获得的物品的总价值。

输入输出数据格式：
- 输入格式：
- 第一行：两个整数 $ n $ 和 $ q $，分别表示物品数量和询问数量。
- 第二行：$ n $ 个整数，表示每个物品的价格 $ p_i $。
- 接下来 $ q $ 行：每行两个整数 $ x_i $ 和 $ y_i $，表示每个询问中的参数 $ x $ 和 $ y $。
- 输出格式：
- 对于每个询问，输出一个整数，表示在这种情况下的最大节省金额。

样例解释：
- 第一种情况：顾客可以购买三个物品，价值分别为 $ 5, 3, 5 $，其中最便宜的两个总价值为 $ 3 + 5 = 8 $。
- 第二种情况：顾客可以购买两个物品，价值为 $ 5 $ 和 $ 5 $，其中最便宜的一个价值为 $ 5 $。
- 第三种情况：顾客需要购买所有物品来免费获得最便宜的三个，总价值为 $ 1 + 2 + 3 = 6 $。题目大意： 一个商店有 $ n $ 个物品，每个物品有各自的价格 $ p_i $。商店计划进行一个优惠活动：如果顾客购买至少 $ x $ 个物品，则其中最便宜的 $ y $ 个物品免费。你需要处理 $ q $ 个询问，对于每个给定的 $ x $ 和 $ y $，计算顾客在一次购买中最多能免费获得的物品的总价值。 输入输出数据格式： - 输入格式： - 第一行：两个整数 $ n $ 和 $ q $，分别表示物品数量和询问数量。 - 第二行：$ n $ 个整数，表示每个物品的价格 $ p_i $。 - 接下来 $ q $ 行：每行两个整数 $ x_i $ 和 $ y_i $，表示每个询问中的参数 $ x $ 和 $ y $。 - 输出格式： - 对于每个询问，输出一个整数，表示在这种情况下的最大节省金额。 样例解释： - 第一种情况：顾客可以购买三个物品，价值分别为 $ 5, 3, 5 $，其中最便宜的两个总价值为 $ 3 + 5 = 8 $。 - 第二种情况：顾客可以购买两个物品，价值为 $ 5 $ 和 $ 5 $，其中最便宜的一个价值为 $ 5 $。 - 第三种情况：顾客需要购买所有物品来免费获得最便宜的三个，总价值为 $ 1 + 2 + 3 = 6 $。