题目描述

在 Goblin Slayer（哥布林杀手）所生活的世界里，哥布林住在山脊上的一排洞穴中。一共有 N 个洞穴，按顺序排在一座长山的山脊上。

当 Goblin Slayer 到访某个洞穴时，他会杀死其中所有哥布林；但由于它们繁殖很快，在隔一天之后，该洞穴中又会重新出现同样数量的哥布林（也就是说，访问后的第二天会恢复，而紧接着的第二天仍然是空的）。

主角的目标是在给定的天数内杀死尽可能多的哥布林。每天他会访问恰好一个洞穴，并在该洞穴前过夜。若第 t 天他访问了第 i 个洞穴，那么第 t+1 天他只能访问相邻的洞穴，也就是 i-1 或 i+1。

在第 1 天开始时，Goblin Slayer 位于位置 0（也就是第一个洞穴左边的位置，而第一个洞穴位于位置 1）。所有洞穴一开始都是满的，第 i 个洞穴中有 Gi 个哥布林。

在真正开始行动之前，他还不确定这次行动会持续多少天。请编写程序 goblins.cpp，回答 Q 个询问。每个询问给出一个 Tj，问如果行动持续 Tj 天，最多能杀死多少个哥布林。

输入格式

第一行两个正整数 N 和 Q，表示洞穴数量和询问数量。
第二行 N 个正整数 G1, G2, ..., GN，表示每个洞穴中的哥布林数量。
接下来 Q 行，每行一个整数 Tj，表示行动持续的天数。

输出格式

输出 Q 行，每行一个正整数，按输入顺序回答对应询问。

数据范围

• 2 ≤ N, Q ≤ 10^6
• 1 ≤ Gi, Tj ≤ 10^7
• 当 j ≠ k 时，Tj ≠ Tk

子任务与评分

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。

• 子任务 1（5 分）：N, Q, Tj ≤ 10
• 子任务 2（10 分）：N, Q, Tj ≤ 15000
• 子任务 3（10 分）：N, Q ≤ 18000
• 子任务 4（20 分）：Gi 与 Tj 为随机生成
• 子任务 5（55 分）：无额外限制

样例输入

4 3
3 1 2 3
3
1
5

样例输出

7
3
11

样例解释

持续 3 天时，最优路线为：1 → 2 → 1。
持续 1 天时，唯一可能的路线是：1。
原题样例说明中写道“持续 4 天时”的最优路线为 1 → 2 → 3 → 4 → 3；这里按原题保留该表述，但该路径本身包含 5 次访问。