Caravans#1894
"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 consists of wagons, each containing some amount of gold. The raid can start at any wagon and then continue to the next or previous wagon, collecting the gold found there. The operation must be carried out quickly; otherwise, the guards will arrive and catch the robbers. As a result, it will not be possible to loot all the wagons.
Kolya, who as expected plays as the elves, knows the number of wagons in the caravan , the amount of gold in each wagon (the -th wagon contains a_i gold), and the maximum number of wagons that his squad can raid before the guards arrive. He must determine the maximum amount of gold that can be collected during the raid.
The first line contains two integers and (1 \leq k \leq N \leq 100000), representing the number of wagons in the caravan and the maximum number of wagons that can be looted. The second line contains integers a_i, the amount of gold in each wagon (0 \leq a_i \leq 10000).
Output a single line with the maximum sum of gold that can be obtained from the raid.
Example 1