思路分析

首先，我们分析分数的计算公式。分数由两部分组成：

P3682.第4题-多多的序列分数

1000ms

Difficulty: 7

所属公司 : 拼多多

算法与标签>贪心算法

多多有一个长度为 $n$ 的序列 $(a_1,a_2,...,a_n)$ ，对于给定的 $x$ 和 $y$ ；

一个序列的分数定义为 $\sum_{1}^{\left\lfloor\frac{n}{x}\right\rfloor} a_{i \cdot x}-\sum_{1}^{\left\lfloor\frac{n}{y}\right\rfloor} a_{j \cdot y}$

序列元素可任意交换位置，得到一个新的序列。多多想知道，经过若干次操作后，新的序列的最大分数是多少。

第一行为 $2$ 个数字， $n,q$ ，其中 $n≤2*10^5,q≤10^4$

接下来 $1$ 行 $n$ 个数字，分别为 $a_1,a_2,...,a_n$ ，其中 $0≤a_1＜10^9$

接下来 $q$ 行，每行两个数字 $x,y$ ，其中 $1≤x,y≤n$

输出 $q$ 行，每行包含一个数字，代表序列的最大分数

输入

7 1
5 9 3 8 2 10 3
2 3

输出

说明

按照题目中的分数定义，序列的分数为

$(a_2+a_4+a_6)-(a_3+a_6)$ ；

经过元素交换后一种可能的序列为

$3$ $9$ $2$ $10$ $8$ $5$ $3$ ，

此时分数最大为 $(9+10+5)-(2+5)=17$

输入

预期输出（选填）