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!
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 q lines, containing the answers for each query.
3 2
5 2 1
1
2
7
12
| KTU Programming Camp (Day 3) |
|---|
| Finished |
