1021 - The Maximum Subsequence with Bounded Length (small version)

Description

Given an array of integers A = a₁, a₂, ..., a_n, a subsequence of A is a sequence of continuous elements in A, that means a sequence of form a_i, a_i+1,..., a_j (1 ≤  i  ≤  j ≤  n). The length of the subsequence is the number of its elements. The weight of the subsequence is the sum of all elements. A subsequence has the bounded length if its length is greater or equal to L₁ and smaller or equal to L₂.

Your task is to find the maximum weight subsequence of A with length bounded by L₁ and L₂.

Input

The fist line contains 4 positive integers n, L₁, L₂ (n ≤  10⁶, L₁ ≤ L₂ ≤ n).

The second line contains n integers a₁, a₂,..., a_n. 

Output

Print uniquely one integer which is the found weight.

Sample Input

6  3  4
3  5 -9  6  7  -4

Sample Output

9

Hint

The Maximum Subsequence with Bounded Length is 5, -9, 6, 7 having the weight 9.

Source

• Submit
• Summary
• Discuss