Average Trick or Treat candy

Every Halloween, EthanPacker loves to go trick or treating, an activity that consists of trick or treaters visiting different houses and obtaining ~C_i~ amount of candy from each house ~i~. This year, he wants to maximize the amount of he candy can obtain before running out of energy. At first, he is dropped off at a single house ~j~ can walk to adjacent houses ~j + 1~ and ~j - 1~ which are both exactly one distance away from each other. For every house EthanPacker passes by (including the one he is dropped off at), he can claim ~C_i~ amount of candy from the house ~i~ exactly once (he cannot visit the same house twice). Throughout the night, EthanPacker can walk a total of ~K~ distance from the starting house before running out of energy. What is the maximum amount of candy EthanPacker can obtain before running out of energy?

Input Specification

The first line of input will contain two integers, ~N~ the number of houses in a row and ~K~ the amount of energy EthanPacker has. The next line will contain ~N~ integers, representing the amount of candy each house ~N_i~ will give out.
Python users are recommended to submit in PyPy3

Output Specification

Output the maximum amount of candy EthanPacker can obtain before he runs out of energy.

Subtasks

~0 \le C_i \le 10^3~

Batch 1 [10%]
~0 \le K < N \le 10~

Batch 2 [20%]
~0 \le K \le 10 < N \le 10^3~

Batch 3 [20%]
~0 \le K < N \le 10^3~

Batch 4 [50%]
~0 \le K < N \le 10^6~

Sample Input 1

10 2
1 2 3 4 5 6 7 8 9 10

Sample Output 1

27

Explanation for Sample Output 1

The maximum amount of candy EthanPacker can obtain is 27.
This can be obtained by being dropped off at house 8, walking to house 9, and then to house 10 for a total distance of 2.
During this walk, he can collect 27 candy from the houses he passes by: 8 candies from house 8, 9 candies from house 9, and 10 candies from house 10.

Sample Input 2

10 4
8 0 2 14 8 3 5 0 9 5

Sample Output 2

32

Explanation for Sample Output 2

There are two ways to obtain this maximum value of 32.
If EthanPacker is dropped of at house 5 and walk 4 units to the left, or he can be dropped of at house 3 and walk 4 houses to the right.
8 + 14 + 2 + 0 + 8 = 32 or 2 + 14 + 8 + 3 + 5.