Wstęp do programowania w C++

Żadna praca nie hańbi, a szczególnie ta, w której można dobrze zarobić. W pewnej firmie "Bittext" oferującej usługi programistyczne, wysokość poborów jest uzależniona od ilości poprawek i błędów programisty. W skrajnej sytuacji programista może popełnić tak dużo błędów, że jego zarobek w ciągu dnia będzie ujemny (pracownik będzie musiał zapłacić firmie daną kwotę). Na szczęście firma jest wyrozumiała i pozwala swoim pracownikom dobrać spójny podciąg dni w danym okresie, z którego będą wypłacane profity. Może się™ okazać‡, że do wypłaty będzie brany tylko jeden dzień. Twoim zadaniem jest określenie optymalnej wartości, którą powinien wziąć pod uwagę programista na przestrzeni n dni.

Wejście

W pierwszym wierszu jedna niewielka liczba określająca liczbę zastawów danych.

Każdy zestaw składa się z dwóch wierszy. Pierwszy określa liczbę dni branych pod uwagę do wypłaty (liczba ta jest nie większa niż 10⁵). W drugim wierszu dla każdego dnia wartość zarobionej kwoty mieszczącej się w przedziale [-20000..20000].

Wyjście

Dla każdego zestawu danych jedna liczba określająca maksymalny zarobek pracownika.

Przykład

Wejście:
1
6
-1 -3 6 -5 6 1

Wyjście:
8