Maximum Subarray Problem

You are given a sequence of integers separated by spaces. Your task is to find the contiguous subarray which has the maximum sum and output both the sum and the subarray itself.

The first line of input contains the space separated integers. The output should contain two lines: the first line is the maximum sum, and the second line is the contiguous subarray (space separated) that gives this maximum sum.

Note: In case all numbers are negative, the result is the maximum (least negative) number and the subarray containing only that number. This problem can be efficiently solved using Kadane's algorithm.

Examples:

Input: 1 -2 3 4 -1 2 1 -5 4
Output:
9
3 4 -1 2 1
Input: -1
Output:
-1
-1

</p>

inputFormat

The input consists of a single line of space separated integers.

outputFormat

The output must contain two lines. The first line contains the maximum sum achievable by any contiguous subarray of the input. The second line contains the contiguous subarray (space separated integers) corresponding to that maximum sum.

## sample

1 -2 3 4 -1 2 1 -5 4

9
3 4 -1 2 1

</p>