Given a sequence of
N numbers. All its continuous subsequences are considered, in which the number of positive numbers
does not exceed C. Find among them the subsequence with the maximum sum, of length
L.
Input
Given two input files (
file A and
file B), each of which contains the first line feeds 3 numbers: the number of numbers N (1 <= N <= 1 000 000), L< /code> and C (\(1 <= L, C <= N <= 1,000,000\)). Each of the following N lines contains a single number not exceeding 1000 modulo.
An example of the organization of source data in the input file (for L = 3 and C = 1):
5 3 1
1
-1
-5
-2
3
You can select multiple sequences in this set, but with a maximum sum of -4 it will be: -5+(-2)+3.
Answer(for C = 3 and L = 1): -4.
In your answer, indicate two numbers on one line separated by a space: first, the value of the required amount for file A, then for file B.
Warning: File B should not be processed by a brute-force algorithm that calculates the sum of all possible options, as the program written in such an algorithm will run too long.