← 返回题目列表

AtCoder · aising2019_d

D. 最近的纸牌游戏

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

分数: 500 点

问题陈述

有 N 卡。的 i第一张卡有一个整数 上面写着 A_i 。 对于任意两张牌,这些牌上的整数都是不同的。

使用这些卡,高桥和青木将玩以下游戏:

  • 青木选择一个整数 x.
  • 从高桥开始,两名玩家轮流拿一张牌。应按以下方式选择卡:
    • 高桥应该拿剩余卡中整数最大的卡。
    • Aoki 应该拿下整数最接近的牌 剩余卡中的 x 。如果有多张这样的牌,他应该拿这些牌中整数最小的牌。
  • 当没有剩余牌时游戏结束。

你被给予 Q 候选人的价值 x: X_1, X_2, ..., X_Q。 对于每个 i (1 \leq i \leq Q),找到如果青木选择,高桥将拿走的卡片上写的整数的总和 x = X_i.

约束

  • 2 \leq N \leq 100 000
  • 1 \leq Q \leq 100 000
  • 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
  • 1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
A_1 A_2 ... A_N
X_1
X_2
:
X_Q

输出

打印 Q 行。的 i- 第行 (1 \leq i \leq Q)应包含以下问题的答案 x = X_i.


示例输入 1

5 5
3 5 7 11 13
1
4
9
10
13

示例输出 1

31
31
27
23
23

例如,当 x = X_3(= 9),游戏进行如下:

  • 高桥拿着卡片 13.
  • 青木拿牌 7.
  • 高桥拿着卡片 11.
  • 青木拿牌 5.
  • 高桥拿着卡片 3.

因此, 13 + 11 + 3 = 27 应打印在第三行。


示例输入 2

4 3
10 20 30 40
2
34
34

示例输出 2

70
60
60