|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
A heavy rain has come to the Bytean Forest. Byteman - an eager mushroom hunter - has decided to take his chance and go mushrooming.
Byteman knows a nice path leading through the forest which contains several glades containing a lot of mushrooms. Every two consecutive glades in the path are equidistant - Byteman needs 15 minutes to walk between any pair of adjacent glades. Having arrived at a glade, Byteman - like any other self-respecting mushroom hunter - collects all mushrooms in this glade in no time. It is a well-known fact that mushrooms... spring up like a mushroom and it takes them only half an hour to grow back after they are collected.
Knowing the numbers of mushrooms growing on respective glades, the duration of Byteman's walk and assuming that he takes a route that maximizes his crops, find the number of mushrooms he will collect. Byteman can finish his walk at any point of the path.
The first line of the standard input contains two integers n and t (1 ≤ n, t ≤ 1 000 000) which denote the number of glades in the path and the duration of Byteman's walk, in quarters. The second line contains a sequence of n integers ai (1 ≤ ai ≤ 1 000 000), representing the numbers of mushrooms in consecutive glades of the path. Byteman starts his walk at the first of these glades. We assume that Byteman can collect mushrooms both just before the first and just after the i-th quarter of mushrooming.
In the first and only line of the standard output your program should output one integer: the maximal number of mushrooms that can be collected by Byteman during his walk.
5 4 3 4 3 5 1
In the optimal Byteman's route, which takes him 60 minutes, he collects 18 mushrooms: 3 at time 0, 4 after 15 minutes, 3 after 30 minutes, 5 after 45 minutes and, finally, 3 after 60 minutes.