You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

你需要按顺序完成 $n$ 道题。

当你的联想能力为 $x$ 时，对于第 $i$ 道题：

• 你可以花费 $a_i$ 时间直接完成第 $i$ 道题；
• 或者用联想的方式完成第 $i$ 道题，即选择一个 $j$ 满足 $1\leq j<i$ 且 $|a_j-a_i|\leq x$，花费 $|a_j-a_i|$ 时间来完成第 $i$ 道题。

有 $q$ 个询问，第 $i$ 个询问求当你的联想能力为 $x_i$ 时，完成 $n$ 道题最少要花费多久时间。

格式

输入格式

第一行包含两个整数 $n,q$，分别表示题的数量和询问的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示直接完成每道题花费的时间。

接下来 $q$ 行每行包含一个整数 $x_i$，表示一个询问。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 个整数为第 $i$ 个询问的答案。

样例

样例输入 #1

4 3
20 54 30 43
10
40
20

样例输出 #1

127
75
95

样例解释 #1

当你的联想能力为 $10$ 时，一种方案为：直接完成第 $1$ 道题，直接完成第 $2$ 道题，从第 $1$ 道题联想完成第 $3$ 道题，直接完成第 $4$ 道题，花费的总时间为 $20+54+|20-30|+43=127$。

当你的联想能力为 $40$ 时，一种方案为：直接完成第 $1$ 道题，从第 $1$ 道题联想完成第 $2$ 道题，从第 $1$ 道题联想完成第 $3$ 道题，从第 $2$ 道题联想完成第 $4$ 道题，花费的总时间为 $20+|20-54|+|20-30|+|54-43|=75$。

当你的联想能力为 $20$ 时，一种方案为：直接完成第 $1$ 道题，直接完成第 $2$ 道题，从第 $1$ 道题联想完成第 $3$ 道题，从第 $2$ 道题联想完成第 $4$ 道题，花费的总时间为 $20+54+|20-30|+|54-43|=95$。

数据规模

对于 $20\%$ 的数据，$n,q\leq 100$。

对于 $60\%$ 的数据，$n,q\leq 3000$。

对于 $100\%$ 的数据，$1\leq n,q\leq 10^5$，$1\leq a_i,x_i\leq 10^9$。