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.

Input
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 .

Output
Print no more than lines. In the line print the sum of the sequence in the above order.

Constraints

Sample Input 00

5 3
2 4 -10 2 -2

Sample Output 00

6
2

Explanation

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

4 2
-2 5 -1 -8

Sample Output 01

5    

Explanation

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.

Tested by Abhiranjan