Mushrooms

A heavy rain has come to the Bytean Forest. Byteman, an eager mushroom hunter, decides to seize the chance and go picking.

The forest has a pleasant path that runs past several glades, and every glade holds some mushrooms. Consecutive glades along the path are equally spaced, so walking from one glade to an adjacent one always takes 15 minutes. On reaching a glade, Byteman instantly picks every mushroom there. Once picked, the mushrooms grow back completely in exactly 30 minutes, and regrown mushrooms can be picked in full again.

Byteman starts at the first glade and, every 15 minutes, walks to a neighbouring glade (he cannot stay in place). The walk lasts $t$ quarter-hour intervals, so he makes $t$ moves in total and picks the mushrooms of whichever glade he stands on at minutes $0, 15, 30, \dots, 15t$. He may end the walk at any glade on the path.

Given the number of mushrooms at each glade and the length of the walk, determine the maximum number of mushrooms Byteman can gather if he moves optimally.

The first line contains the number of glades $n$ and the length of the walk $t$ ($1 \le n, t \le 10^6$), where $t$ is the number of 15-minute intervals, that is, the number of moves Byteman makes.

The second line contains the mushroom counts $a_1, a_2, \dots, a_n$ of the glades in order along the path ($1 \le a_i \le 10^6$). Byteman starts at the first glade. At the moment exactly 30 minutes after a glade is picked, its mushrooms may already be picked again.

Print a single integer: the maximum number of mushrooms Byteman can gather during the walk.

Consider $n = 5$, $t = 4$ and mushroom counts 3 4 3 5 1. In an optimal 60-minute (four-interval) route Byteman gathers 18 mushrooms: 3 at minute 0, 4 after 15 minutes, 3 after 30 minutes, 5 after 45 minutes, and finally 3 more after 60 minutes. The glade picked at minute 30 has fully regrown exactly 30 minutes later, at minute 60, so it can be picked once more.