Subsequence with K numbers
Problem
Given a sequence of
N numbers. All its continuous subsequences are considered that contain exactly
K negative numbers ending with the digit
m. Find among them the subsequence with the maximum sum. The program should output a single number – the maximum sum of the elements of such a subsequence. It is guaranteed that the source sequence contains at least
K negative numbers ending in
m.
Input
The first line of the program produces three numbers: the number of numbers in the sequence
N (100 <= N <= 5000000), the natural number
K and the natural number
m< /code> (0 <= m <= 9). The each of the following N lines contains one integer not exceeding 10000 in modulo. It is guaranteed that the sum of any subsequence of the original sequence does not exceed modulo 109.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
8 2 3
6
-3
-2
4
-1
-13
8
13 |
12 |
The numbers we need are -3 and -13. The entire original sequence will give the maximum sum of elements. |