Maximum Subarray (Kadane's Algorithm)

Ashgrove Coffee logs each day's profit or loss as a single number — positive on a good day, negative on a bad one. The owner wants to advertise the shop's best run: an unbroken stretch of consecutive days whose profits add up to as much as possible. Skipping a bad day in the middle is not allowed, because the claim is about a continuous period. Some shops have never had a profitable day at all, and the best run still has to be reported.

Task: Print the largest total that any unbroken stretch of days can add up to.

Input

A single line holding between 1 and 100000 integers separated by single spaces — one day's result per number, in date order. Values may be negative, zero or positive.

Output

One line holding a single integer: the largest total. The stretch must be made of consecutive days and must contain at least one day, so when every day is a loss the answer is the single smallest loss rather than 0.

Example:

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

Output:
6

(the subarray [4, -1, 2, 1] sums to 6)