Supermarket

A supermarket offers gift vouchers to its customers in the following way. The customer places the products in a sequence on the checkout belt, and the cashier, as she charges them, when she reaches the product that is at a multiple position of the number K, gives a gift voucher to the customer equal to the value of that product. For example, for ~K = 3~, vouchers equal to the value of the third product, the sixth, the ninth, etc., are given.

Thanasis has placed the N products he has purchased on the belt in a random order and he knows that the price of the ~i~-th product (in the order he has placed them) is A~\mathbf{_i}~. Then, he learns about the vouchers and finds out the value of K. Of course, he would like to maximize the total value of the vouchers he will receive. However, he doesn't have time to rearrange all his products. The only thing he can do is to go through them once, starting from the one closest to the checkout, and (if he wants) to move some products to the end of the queue. However, he can make at most M such moves, and he cannot move the same product twice.

Problem

Write a program in one of the languages of the IOI that reads the values of ~N~, ~M~, and ~K~, the values of the products ~A_i~ that Thanasis wants to buy, and finds the maximum possible total value of the vouchers he can win.

Input Files:

The input files named supermarket.in are text files consisting of two lines: The first line contains three integers separated in pairs by a single space: the values of N, M, and K ~(1 \le K \le N \le 100.000,\;0 \le M \le 500)~. The second line contains ~N~ integers A~\mathbf{_i}~ ~(1 \le A_i \le 10.000.000)~, separated in pairs by a single space: the values of the products in their original order. The sum of all ~A_i~ will not exceed ~1.000.000.000~.

Output Files:

The output files named supermarket.out are text files consisting of exactly one line containing exactly one integer: the maximum possible total value of the vouchers Thanasis can receive.

Examples of Input - Output Files:

1st

STDIN (supermarket.in)

5 1 2
10 2 6 4 8

STDOUT (supermarket.out)

14

Explanation of the first example:

In the first example, Thanasis can choose to move the first product (worth ~10~) to the end, so the final sequence that the cashier will charge his products with will be ~2~, ~6~, ~4~, ~8~, ~10~. Therefore, the total value of the vouchers he will receive will be ~6 + 8 = 14~. This is the maximum possible in this case.

2nd

STDIN (supermarket.in)

5 2 2
10 1 1 1 10

STDOUT (supermarket.out)

11

Explanation of the second example:

In the second example, despite being able to move two products, Thanasis has no way to arrange his products in such a way as to receive vouchers for the two "tens". One way to achieve the maximum possible value is to move one of the "aces" to the end, so the final sequence will be ~10~, ~1~, ~1~, ~10~, ~1~. Then, the total value of the vouchers he will receive will be ~1 + 10 = 11~.

Scoring:

In at least 25% of the test cases, ~M < N \le 100~. Additionally, in all test cases, at least one of the following conditions will hold:

• ~N \le 500~ and ~M \le 500~
• ~N \le 1.000~ and ~M \le 300~
• ~N \le 10.000~ and ~M \le 100~
• ~N \le 100.000~ and ~M \le 10~

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 2 sec.
Maximum available memory: 64 MB.