402377: GYM100739 K Easy vector

Memory Limit:64 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Easy vectortime limit per test0.75 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

You're given a vector with n elements. Piro starts from cell 1. He walks x seconds. In each second, he can move to an adjacent cell: for a cell i with 2 ≤ i ≤ n, he can move to i - 1 and i + 1. From cell 1 he can only move to cell 2 and from cell n he can only move to cell n-1.

Initially, his sum is what's written on cell 1, from where he starts. Next x seconds, his sum increases by what's written on each cell he visits during those x seconds. What's the maximum sum he can get? Formally, given vector A, choose i1, i2, ..., ix such as you maximize the sum A[1] + A[i1] + A[i2] + ... + A[ix], where 1 ≤ ik ≤ n and |ik - ik - 1| = 1.

Given an array and q queries, each query containing a value x, please answer all of them!

Input

The first line contains numbers n and q (1 ≤ n, q ≤ 105, n is at least 2). Next n lines contain the values of vector: each element of vector is between 1 and 105. Next q lines contain values of queries: each lines contains a new value for x (1 ≤ x ≤ 109).

Output

Output q lines, containing the answers for each query.

ExamplesInput
3 2
5 2 1
1
2
Output
7
12

加入题单

上一题 下一题 算法标签: