Blade of Gold

You are given n materials, numbered from 1 to n. The i-th material has a sturdiness value \(a_i\). The process of alchemy requires that you add these materials into the cauldron strictly in the order from 1 to n.

The cauldron has a capacity limit: it can hold at most \(w\) materials at any time. Fortunately, before adding each material, you are allowed to remove at most \(s\) materials from the cauldron.

The durability contribution when adding the i-th material is defined as the current number of materials in the cauldron (including the one just added) multiplied by \(a_i\). The overall durability of the golden sword is the sum of these contributions for all materials.

Determine the maximum possible total durability of the sword.

Note: When computing the contribution of a material, the material being added is included in the number of materials in the cauldron.

inputFormat

The input consists of two lines:

• The first line contains three integers \(n\), \(w\), and \(s\) -- the number of materials, the capacity of the cauldron, and the maximum number of materials you may remove before adding a new material, respectively.
• The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\), representing the sturdiness values of the materials.

outputFormat

Output a single integer -- the maximum possible total durability of the sword.

sample

3 2 1
5 3 2

23