Welcome Back Contest: 2025 Problem 5

Mr. Rich has lots of money! He decides that he wants to buy multiple rental houses to make some passive income. He wants to buy houses in a newly built street of a neighbourhood with ~N~ houses, numbered ~1~ to ~N~ from left to right. Each house has cost, the ~i~-th of which having a cost of ~c_i~ dollars.

Being a newly built street, all the houses are available for purchase. Mr. Rich wants to spend as much money as possible, and so he will buy houses such that the total value of all the houses he buys is maximized. However, he won't buy houses that are too close together (due to regulations from the local government) and he also doesn't want to buy houses too far apart. More specifically, a house and its closest neighbour on the left and right (if they exist) must not have less than ~K - 1~ or more than ~M - 1~ houses in between them.

Note that it is possible for Mr. Rich to purchase just one house.

Please help Mr. Rich figure out what is the most amount of money he can spend on houses.

Input Specification

The first line contains the integers ~N~, ~K~, and ~M~, each separated by a space.

The next line contains the prices of the ~N~ houses, each separated by a space, from house ~1~ to ~N~.

Output Specification

Output the total value of all the houses Mr. Rich can purchase.

Subtasks

~1 \le K \le M \le N \le 10^5~

~1 \le c_i \le 10^4~

Subtask 1 [50%]

~1 \le K \le N \le 10^3~

Subtask 2 [50%]

No additional constraints

As an extra challenge, try to have your program run in linear time!

Sample Input 1

10 3 6
3 5 2 2 3 5 6 7 9 2

Output for Sample Input 1

19

Explanation of Output for Sample Input 1

Houses number ~2~, ~6~, and ~9~ can be bought for a maximum total cost of ~\$ 5 + \$ 5 + \$ 9 = \$ 19~. Each each house is within ~6~ houses of its closest neighbour on both its left and right side but not closer than ~3~.

Sample Input 2

5 2 5
1 5 7 5 1

Output for Sample Input 2

10

Explanation of Output for Sample Input 2

Houses number ~2~ and ~4~ can be bought for a maximum total cost of ~\$ 5 + \$ 5 = \$ 10~. Each each house is within ~5~ houses of its closest neighbour on both its left and right side but not closer than ~2~.

Sample Input 3

9 3 4
4 1 9 1 2 2 1 8 2

Output for Sample Input 3

14

Sample Input 4

6 1 2
1 2 3 4 5 6

Output for Sample Input 4

21

Explanation of Output for Sample Input 4

All of the houses can be bought in this case.