During a math class, a teacher wanted to practice ordering with students. He gave an array of integers, to the students along with following definitions:
Subarray is a contiguous segment of array. For example is a subarray, where
We say that a sum of a subarray is a sum of elements in this subarray
We say that subarray is greater than subarray if and only if:
has a greater sum than
and has the same sum and begins earlier
and has the same sum, they start in the same place and the length of is smaller than the length of
Since the teacher doesn't like number 0, there is no 0 in the array . Other than array , the teacher also gave an integer . The task is to lists as many as possible, but not more than , subarrays with a positive sum in the following order.
The first subarray is the greatest subarray in the array according to above definition.
The subarray is the greatest subarray disjoint to any of the subarray, where (disjoint means that they have no common elements).
Of course in order to win with others, you have to solve the problem first.
In the first line there are two integers and separated by a single space.
In the second line there are integers separated by single space denoting the array .
Print no more than lines. In the line print the sum of the sequence in the above order.
Sample Input 00
2 4 -10 2 -2
Sample Output 00
Subarray has sum 6 and this is the greatest value in the whole array. Next disjoint greatest subarray is with sum = 2. There are no more subsequences with a positive value disjoint with the first and the second subsequence.
Sample Input 01
-2 5 -1 -8
Sample Output 01
Subarray has sum 5 and this is the greatest value in the whole array. There are no more subsequences with a positive value disjoint with the first one, so even if K = 2, we print out just one value.