Let $$$A$$$ be an array of positive integers. Let you are playing a Game.

Initially your score is $$$0$$$.

Let you start from index $$$0$$$. In one move you can go from current cell $$$i$$$ to any adjacent cell i.e (either $$$i-1$$$ or $$$i+1$$$ if they exist). you can visit a cell any number of times. when you visit any cell $$$i$$$, then $$$A[i]$$$ is added in your score.

you should make exactly $$$k$$$ such moves.

what is the maximum possible value of score?

**Example**

if arr is $$$[7, 8, 7 ,9 , 5]$$$

and $$$k = 4$$$, then ans is $$$38$$$

i.e you can move like this : $$$0 -> 1 -> 2 -> 3 -> 2$$$

**Constraint**:

$$$k < 10^6$$$

$$$N < 10^6$$$

$$$A[i] < 10^6$$$

The best i can think of it's $$$O(n*k)$$$ solution using dynamic programming, which definitely times out.