Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def load_input():
    n, k = list(map(int, input().split()))
    s = list(input())
    return n, k, s


def main():
    n, k, s = load_input()

    max_len = 0
    init_pos = 0
    while True:
        next_init = False
        order = k
        current = 1
        prev = s[init_pos]
        if s[init_pos] == '0':
            order -= 1
        for i in range(init_pos + 1, len(s)):
            if prev != s[i]:
                if s[i] == '0':
                    if 0 < order:
                        order -= 1
                    else:
                        if max_len < current:
                            max_len = current
                        break
                else:
                    if next_init is False:
                        next_init = True
                        init_pos = i
            prev = s[i]
            current += 1
        if max_len < current:
            max_len = current
        if next_init is False:
            break
    print(max_len)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1

    while first <= last:
        midpoint = (first + last)//2
        if item < alist[midpoint] and alist[midpoint - 1] < item or midpoint == 0 and item < alist[midpoint]:
            return midpoint
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return -1


def load_input():
    n, k = list(map(int, input().split()))
    s = list(input())
    return n, k, s


def main():
    n, k, s = load_input()

    starts = [0]
    ends = []
    for i in range(n):
        if 0 < i and s[i - 1] == '1' and s[i] == '0':
            ends.append(i)

        if 0 < i and s[i - 1] == '0' and s[i] == '1':
            starts.append(i)
    ends.append(n)

    ml = 0
    for start in starts:
        order = k
        if start == 0 and s[0] == '0':
            order -= 1
        i = binarySearch(ends, start)
        if i + order < len(ends):
            end = ends[i + order]
        else:
            end = ends[-1]
        if ml < end - start:
            ml = end - start
    print(ml)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from itertools import product
H,W,M = map(int,input().split())
h_list = [0] * M
w_list = [0] * M
for m in range(M):
    h_list[m],w_list[m] = map(int,input().split())
hh_list = [0] * H
ww_list = [0] * W
for m in range(M):
    hh_list[h_list[m]-1] += 1
for m in range(M):
    ww_list[w_list[m]-1] += 1
h_max = max(hh_list)
w_max = max(ww_list)

h_ans = []
w_ans = []

for hh in range(H):
    if hh_list[hh] == h_max:
        h_ans.append(hh)
for ww in range(W):
    if ww_list[ww] == w_max:
        w_ans.append(ww)
cnt = 0
for i,j in zip(h_list,w_list):
    if i-1 in set(h_ans) and j-1 in set(w_ans):
        cnt += 1
if cnt == len(h_ans) * len(w_ans):
    print(h_max + w_max - 1)
else:
    print(h_max + w_max)

### FIXED CODE ###

from itertools import product
H,W,M = map(int,input().split())
h_list = [0] * M
w_list = [0] * M
for m in range(M):
    h_list[m],w_list[m] = map(int,input().split())
hh_list = [0] * H
ww_list = [0] * W
for m in range(M):
    hh_list[h_list[m]-1] += 1
for m in range(M):
    ww_list[w_list[m]-1] += 1
h_max = max(hh_list)
w_max = max(ww_list)

h_ans = []
w_ans = []

for hh in range(H):
    if hh_list[hh] == h_max:
        h_ans.append(hh)
for ww in range(W):
    if ww_list[ww] == w_max:
        w_ans.append(ww)
cnt = 0
h_set = set(h_ans)
w_set = set(w_ans)
for i,j in zip(h_list,w_list):
    if i-1 in h_set and j-1 in w_set:
        cnt += 1
if cnt == len(h_ans) * len(w_ans):
    print(h_max + w_max - 1)
else:
    print(h_max + w_max)
### BUGGY CODE ###

N = input()
N = int(N)
if not(1 <= N and N <= 10**9):
    exit()

n_list = []
num = 1
for i in range(N):
    n_list.append(i+1)
    num = num * (i+1)

ans = 0
# i = 0
# for i in range(num):
#     print(i+1)
#     P = []

# print(n_list)



# ans = 0

tmp = n_list.pop(0)
n_list.append(tmp)
# print(n_list)

for i in range(len(n_list)):
    ans += (i+1) % n_list[i]

# P = []
# for i in n_list:
#     P.insert(0, i)

# print(P)
print(ans)

### FIXED CODE ###

N = input()
N = int(N)
if not(1 <= N and N <= 10**9):
    exit()
ans = 0

if N % 2 == 0:
    i = int(N/2)
    ans = (N+1) * i
    ans -= N
else:
    i = int(N/2)
    ans = N * i

    
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
for i, l in enumerate(a):
    tmp = copy.deepcopy(a)
    tmp.pop(i)
    print(max(tmp))

### FIXED CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
ans = max(a)
n_a = copy.deepcopy(a)
n_a.remove(ans)
s_ans = max(n_a)
if s_ans == ans:
    for i in a:
        print(ans)
else:
    for i in a:
        if i == ans:
            print(s_ans)
        else:
            print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
for i in range(n):
    ans = p[:i+1]
    if min(ans) != p[i]:
        count += 1
print(n-count)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
mi = n+1
for i in range(n):
    mi = min(mi,p[i])
    if mi == p[i]:
        count += 1
print(count)
### BUGGY CODE ###

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))

M = max(C)+1
t1 = [0]*(M)
for v in C:
    t1[v] = 1

t2 = [0]*(M)
v = 0
for i in range(M):
    if t1[i]:
        v = i
    t2[i] = v

for i in range(Q):
    t = int(input())
    n_v = M-1
    m = 0
    while n_v != 0:
        amr = n_v % t
        m = max(m,amr) 
        n_v = t2[n_v-1]

    print(m)

### FIXED CODE ###

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))

M = max(C)+1
t1 = [0]*(M)
for v in C:
    t1[v] = 1

t2 = [0]*(M)
v = 0
for i in range(M):
    if t1[i]:
        v = i
    t2[i] = v

for i in range(Q):
    t = int(input())
    n_v = M-1
    m = 0
    while n_v != 0:
        amr = n_v % t
        m = max(m, amr) 
        tmp = n_v-m-1
        if tmp <= 0: break
        n_v = t2[tmp]

    print(m)
### BUGGY CODE ###

# 幅優先探索 #双方向探索
import sys
import queue

SPACE = 0

adjacents_list = (
    (1, 3),       # 0
    (0, 2, 4),    # 1
    (1, 5),       # 2
    (0, 4, 6),    # 3
    (1, 3, 5, 7), # 4
    (2, 4, 8),    # 5
    (3, 7),       # 6
    (4, 6, 8),    # 7
    (5, 7)        # 8
)

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = [start]
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if board in history:
                 continue
            if board == goal:
                return go_back(state)
            history.append(board)
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print(mininum_steps(initial_board, goal))



### FIXED CODE ###

# 幅優先探索 #双方向探索
import sys
import queue

SPACE = 0

adjacents_list = (
    (1, 3),       # 0
    (0, 2, 4),    # 1
    (1, 5),       # 2
    (0, 4, 6),    # 3
    (1, 3, 5, 7), # 4
    (2, 4, 8),    # 5
    (3, 7),       # 6
    (4, 6, 8),    # 7
    (5, 7)        # 8
)

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = {}
    history[tuple(start)] = True
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if tuple(board) in history:
                 continue
            if board == goal:
                return go_back(state)
            history[tuple(board)] = True
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print(mininum_steps(initial_board, goal))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
numbers = []
answers = []
for i in range(Q):
    numbers.append(list(map(int, input().split())))
    answers.append(S[numbers[i][0]-1:numbers[i][1]].count('AC'))
for answer in answers:
    print(answer)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
data = [0] * (N+1)
for i in range(N):
    data[i+1] = data[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r =map(int, input().split())
    print(data[r-1] - data[l-1])
### BUGGY CODE ###

def main():
  h, w = map(int, input().split())
  s = [input() + '#' for _ in range(h)]
  s.append('#' * (w + 1))

  rt = [[-1] * w for _ in range(h + 1)]

  result = 0
  tstart = [-1] * (w + 1)
  for i in range(h + 1):
    si = s[i]
    rti = rt[i]
    ystart = -1
    for j in range(w + 1):
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in range(ystart, j):
            rti[k] += jy
            if rti[k] > result:
              result = rti[k]
          ystart = -1
        if tj != -1:
          itj = i - tj
          for k in range(tj, i):
            rt[k][j] += itj
            if rt[k][j] > result:
              result = rt[k][j]
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i

  print(result)

main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

n = int(input())
a = (int(x) for x in input().split())

res = 1
for x in a :
    res = res * x

if (res > 1e18) :
    print(-1)
else :
    print(res)

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))

    if a.count(0) >= 1:
        print(0)
        return

    res = 1
    for x in a:
        res *= x
        if (res > 10 ** 18):
            print(-1)
            return
    print(res)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

slp = [map(int,raw_input().split()) for _ in range(int(raw_input()))]
dp = [0]*400
for s,l,p in slp:
    for i in range(s,l+1): dp[i] = max(dp[i],p)

for s,l,p in slp:
    for i in range(s,400-s):
        if dp[i]:
            for j in range(i+s,min(399,i+l+1)):
                dp[j] = max(dp[j],dp[i]+p)

ans = []
for roop in range(int(raw_input())):
    w = int(raw_input())
    if dp[w] == 0:
        print -1
        break
    ans.append(dp[w])
else:
    for a in ans: print a

### FIXED CODE ###

slp = [map(int,raw_input().split()) for _ in range(int(raw_input()))]
maxp = [0]*400

for s,l,p in slp:
    for i in range(s,l+1): maxp[i] = max(maxp[i],p)

dp = maxp[:]
for i in range(399):
    for l in range(1,400-i):
        dp[i+l] = max(dp[i+l],dp[i]+maxp[l])

ans = []
for roop in range(int(raw_input())):
    w = int(raw_input())
    if dp[w] == 0:
        print -1
        break
    ans.append(dp[w])
else:
    for a in ans: print a
### BUGGY CODE ###

N = int(input())
mlist = list(map(int,input().split()))

s = 1
for i in mlist:
    s *= i

if s <= 10**18:
    print(s)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
mlist = list(map(int,input().split()))

s = 1
for i in range(N):
    if mlist[i] == 0:
        print(0)
        s = 0
        break
    elif s > 0:
        s *= mlist[i]

    if s > 10 ** 18:
        s = -1
if i == N-1 and s != 0:
    print(s)
### BUGGY CODE ###

while 1:
    n = input()
    if n==0: break
    s = [0 for i in range(7)]
    for i in range(n):
        age = input()
        s[age/10 if age<60 else 6] += 1
    for i in range(7):
        print s[i]

### FIXED CODE ###

while 1:
    n = input()
    if n==0: break
    s = [0 for i in range(13)]
    for i in range(n):
        s[int(raw_input())/10] += 1
    for i in range(6):
        print s[i]
    print sum(s[6:])
### BUGGY CODE ###

X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
while(True):
    if P[0] >= R[0] and Q[0] >= R[0]:
        break
    if P[0] > Q[0]:
        if Q[0] < R[0]:
            Q[0] = R[0]
            Q = sorted(Q)
            R = R[1:]
    else:
        if P[0] < R[0]:
            P[0] = R[0]
            P = sorted(P)
            R = R[1:]
    if len(R) == 0:
        break
print(sum(P) + sum(Q))

### FIXED CODE ###

import heapq
 
X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
heapq.heapify(P)
heapq.heapify(Q)
i = 0
while(True):
    if P[0] >= R[i] and Q[0] >= R[i]:
        break
    if P[0] > Q[0]:
        if Q[0] < R[i]:
            heapq.heappop(Q)
            heapq.heappush(Q, R[i])
    else:
        if P[0] < R[i]:
            heapq.heappop(P)
            heapq.heappush(P, R[i])
    i += 1
    if i == len(R):
        break
print(sum(P) + sum(Q))
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n, a, b = map(int, input().split())

mod = 10 ** 9 + 7
ans = 2 ** n - 1

ans -= (cmb(n, a) + cmb(n, b))

print(ans % mod)


### FIXED CODE ###

def cmb(n, r, mod):
    numerator = 1
    # n * (n-1) * ... * (n-r+1)
    for i in range(n-r+1, n+1):
        numerator = (i * numerator) % mod
    denominator = 1
    # r * (r-1) * ... * 1
    for i in range(1, r+1):
        denominator = (i * denominator) % mod
    # y^(mod-2) % mod
    fermat = pow(denominator, mod-2, mod)
    return (numerator * fermat) % mod


n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

ans = pow(2, n, mod) - 1
ans -= (cmb(n, a, mod) + cmb(n, b, mod))

print(ans % mod)
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10**10000000000000000000000000000000000000)
a,b = map(int,input().split())
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
if b != 0:
    print(lcm(a, b))
else:
    print(a)

### FIXED CODE ###

from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
a,b = map(int,input().split())
def lcm(x, y):
    return (x * y) // gcd(x, y)
if b != 0:
    print(lcm(a, b))
else:
    print(a)
### BUGGY CODE ###

from collections import deque

s=deque(list(input()))
q=int(input())

for i in range(q):
  l=list(input().split())
  if len(l)==1:
    s.reverse()
  else:
    t,f,c=l[0],l[1],l[2]
    if f=='1':
      s.appendleft(c)
    else:
      s.append(c)

s=list(s)
print(''.join(s))

### FIXED CODE ###

from collections import deque

s=deque(list(input()))
q=int(input())


rev=0
for i in range(q):
  l=list(input().split())
  if len(l)==1:
#    s.reverse()
    rev+=1
  else:
    t,f,c=l[0],l[1],l[2]

    if rev%2==0:
      if f=='1':
        s.appendleft(c)
      else:
        s.append(c)
    else:
      if f=='1':
        s.append(c)
      else:
        s.appendleft(c)

s=list(s)
if rev%2==1:
  s.reverse()
print(''.join(s))
### BUGGY CODE ###

from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = ( end - start ) // 2 
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) ) 
    ans *= sum_c
    start = i + 1
    
if i > -1:
    print( ans % 1000000007 )
else:
    print(0)

### FIXED CODE ###

N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )

break_list.append(-10)
t = 0
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
    t += 1
else:
    fib[1] = 1
    
fib[0] = 1

for i in range(N - 1):
    if ( i + 2 ) ==  break_list[t]:
        fib[i + 2] = 0
        t += 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )
### BUGGY CODE ###

INF = 10**9
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0

for i in range(1, N):
    MIN = INF
    for l in range(K):
        if i-(l+1) >= 0:
            MIN = min(MIN, dp[i - (l + 1)] + abs(h[i] - h[i - (l + 1)]))
    dp[i] = MIN
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [[10**9 for _ in range(K+1)] for _ in range(N)]
dp[0] = [0 for _ in range(K+1)]

for i in range(N):
    for l in range(K):
        if i-(l+1) >= 0:
            dp[i][l] = dp[i - (l + 1)][K] + abs(h[i] - h[i - (l + 1)])
        else:
            dp[i][l] = min(dp[i])
        if l == K-1:
            dp[i][K] = min(dp[i])
print(min(dp[N-1]))
### BUGGY CODE ###

N=int(input())
S=[input() for _ in range(N)]

S=sorted(S)
T=[]
m=S.count(S[0])
T.append(S[0])
for i in range(1,N):
    if S[i]==S[i-1]:
        continue
    if S.count(S[i])>m:
        m=S.count(S[i])
        T.clear()
        T.append(S[i])
    elif S.count(S[i])==m:
        T.append(S[i])
for j in range(len(T)):
    print(T[j])




### FIXED CODE ###

from collections import Counter
N=int(input())
S=[input() for _ in range(N)]

C=Counter(S)
A=[]
B=[]
T=[]

for i,j in C.most_common():
    A.append(i)
    B.append(j)
for k in range(len(A)):
    if B[k]==B[0]:
        T.append(A[k])
T=sorted(T)
for m in range(len(T)):
  print(T[m])
### BUGGY CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    counts[num] += 1
    d *= 10

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2
    
print(ans)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

a,s=map(int,input().split())
l=list(input())
for i in range(s):
  p,q=map(int,input().split())
  c=0
  for o in range(p,q):
    if l[o-1]=="A" and l[o]=="C":
      c+=1
  print(c)
    

### FIXED CODE ###

n,m=map(int,input().split())
l=list(input())
list=[0]
c=0
for i in range(len(l)-1):
  if l[i]=="A" and l[i+1]=="C":
    c+=1
    list.append(c)
  else:
    list.append(c)
for i in range(m):
  n,m=map(int,input().split())
  print(list[m-1]-list[n-1])
### BUGGY CODE ###

D, G = map(int, input().split())
pc = [[i + 1] + [int(x) for x in input().split()] for i in range(D)]

import math, copy
m = {}
def f(cur, n, pc, left):
    if left <= 0:
        return n
    def g(cur, n, pc, left):
        fp = (cur, left)
        if fp in m: return m[fp]
        m[fp] = f(cur, n, pc, left)
        return m[fp]
    ret = 10**9
    for x in pc:
        i, p, c = x
        if i*100*p > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            nc = copy.copy(cur)
            nc.add(i)
            npc = copy.copy(pc)
            npc.remove(x)
            h = f(nc, n + p, npc, max(0, left - i*100*p - c))
            ret = min(ret, h)
    return ret

print(f(set(), 0, pc, G))

### FIXED CODE ###

D, G = map(int, input().split())
pc = [[i + 1] + [int(x) for x in input().split()] for i in range(D)]

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if (1 << i) & cur: continue
        ip = i*100*p
        if ip > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            if n + p >= ret: continue
            h = g(cur | (1 << i), n + p, left - ip - c)
            ret = min(ret, h)
    return ret

print(f(0, 0, G))
### BUGGY CODE ###

from __future__ import (absolute_import, division, print_function,
                        unicode_literals)
from sys import stdin

while True:
    n = int(stdin.readline())
    if not n:
        break

    tup = tuple(int(stdin.readline()) for _ in xrange(n))
    L = [tup[0]]
    for i in tup[1:]:
        if 0 > i and 0 > L[-1]:
            L[-1] += i
        elif 0 <= i and 0 <= L[-1]:
            L[-1] += i
        else:
            L.append(i)

    m = 0
    for i in xrange(len(L)):
        for j in xrange(1 + i, len(L) + 1):
            t = sum(L[i:j])
            if t > m:
                m = t
    print(m)

### FIXED CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from array import array

def grouping(nums):
    sign = None
    L = array(b'i')
    for s, n in ((i < 0, i) for i in nums):
        if sign is s:
            L[-1] += n
        else:
            sign = s
            L.append(n)

    if len(L) and L[-1] <= 0:
        del L[-1]
    if len(L) and L[0] <= 0:
        del L[0]
    return L

while True:
    n = int(stdin.readline())
    if not n:
        break

    L = array(b'i', (int(stdin.readline()) for _ in xrange(n)))
    val = max(L)
    if val <= 0:
        print(val)
        continue

    ans, temp = 0, 0
    for i in grouping(L):
        temp = max(0, temp+i)
        ans = max(ans, temp)
    print(ans)