0.SY. The Maximum Subsequence with Bounded Length


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 293M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Given an array of integers A = a1; a2;.....an, a subsequence of A is a sequence of continuous elements in A, that means a sequence of form ai; ai+1; : : : ; aj (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 L1 and smaller or equal to L2.

Your task is to ?nd the maximum weight subsequence of A with length bounded by L1 and L2.

Input

The ?st line contains 4 positive integers n;L1;L2 (n = < 106;L1 = < L2 = < n).

The second line contains n integers a1; a2;.....; an.

Output

Print uniquely one integer which is the found weight.

Examples

Input

6 3 4

3 5 -9 6 7 -4

Output

9

Dy con di hn ch c trng s ln nht l dy 5, -9, 6, 7 vi trng s bng 9.


Comments

There are no comments at the moment.