import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V
main=print.solve.unfoldr(B.readInt.B.dropWhile isSpace)=<<B.getContents
solve(n:k:ps)=(/2).fromIntegral.(+k).V.maximum.(V.zipWith(-)=<<V.drop k).V.scanl'(+)0.V.fromList$ps