Given a sequence of
N numbers. All its continuous subsequences are considered, in which the number of negative numbers
does not exceed C. Find among them a subsequence with the maximum sum, 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 = 3):
5 3 3
1
-1
2
-2
3
Several sequences can be selected in this set, but with a maximum sum of 3 it will be: 2+(-2)+3.
Answer(for С = 3 and L = 3): 3. ;
In your answer, indicate two numbers: first, the value of the required amount for file A, then for file B.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.