Caravans
"Hello. I am Kyrylo. I would like you to develop a 3D action game with the following concept... Players can choose to be forest elves, palace guards, or a thief. If playing as elves, they reside in the forest with wooden houses, and are attacked by palace soldiers and thieves. Players can raid caravans... [skipped] P.S. I've wanted such a game for two years."
Letter to the game development company MiST land
Naturally, Petryk couldn't overlook the desires of the global gaming community during development. Thus, in his game, players can "raid" and "loot caravans." A caravan is made up of wagons, each holding a certain amount of gold. The raid can begin at any wagon, proceeding to the next or previous one, collecting the gold found there. The operation must be swift to avoid the arrival of guards who will capture the robbers. Consequently, not all wagons can be looted.
Kolya, who predictably plays as the elves, knows both the number of wagons in the caravan N and the amount of gold in each wagon (the i-th wagon contains a_i gold). He also knows the maximum number of wagons k that his squad can raid before the guards arrive. He needs to determine the maximum amount of gold he can collect during the raid.
Input
The first line contains two integers N and k (1 ≤ k ≤ N ≤ 100000), representing the number of wagons in the caravan and the maximum number of wagons that can be looted. The second line contains N integers a_i, indicating the amount of gold in each wagon (0 ≤ a_i ≤ 10000).
Output
Output a single line with the maximum sum of gold that can be obtained from the raid.