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

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for _, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))


### FIXED CODE ###


from collections import Counter
import sys

sys.setrecursionlimit(10**6)


N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for h, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))
### BUGGY CODE ###

DP = {}

def solve(n, a, b, c, d):
    if n <= 0: 
        return 0
    if n == 1:
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()


### FIXED CODE ###

DP = {}

def solve(n, a, b, c, d):
    if n <= 0: 
        return 0
    if n == 1:
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-3, 4):
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7
 
debug = True
debug = False
 
def dprint(*objects):
    if debug == True:
        print(*objects)
 
def main():
    N = II()
    a_list = []
 
    for i in range(N):
        a = II()
        a_list.append(a)
 
 
    g = []
 
    from bisect import bisect_left
 
    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.append(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                g.insert(0, a)
    dprint(g)
    print(len(g))
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    from bisect import bisect_left
    from collections import deque
    g = deque()

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.appendleft(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                #g.insert(0, a)
                g.appendleft(a)
    dprint(g)
    print(len(g))
main()
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v


DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
			DP[i][j][0]=max(DP[i][j][0],DP[i-1][j][ii])
			if v!=0:
				DP[i][j][1]=max(DP[i][j][1],DP[i-1][j][ii]+v)
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)


### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

def mkDivisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors


def main():
    x = ni()
    div = mkDivisors(x)
    for i in div:
        for n in [i,-1*i]:
            for b in range(-n-125, n+125):
                a = b + n
                if pow(a,5) - pow(b,5) == x:
                    print(a,b)
                    return
    print("Erorr")
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    x = ni()
    xmod10 = x%10
    for a in range(-125, 125):
        for b in range(-125, 125):
            if (a-b)%10 == xmod10:
                if pow(a,5) - pow(b,5) == x:
                    print(a,b)
                    return
    print("Erorr")
    return


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

n=int(input())
s=input()
a=[]
for i in range(n):
    a.append(s[:i].count('W')+s[i+1:].count('E'))
print(min(a))

### FIXED CODE ###

n=int(input())
s=input()
w,e=0,s.count('E')
for i in s:
    if i =='W':
        n=min(n,w+e)
        w+=1
    else:
        e-=1
        n=min(n,w+e)
print(n)
### BUGGY CODE ###

N = int(input())
A = {}
for i in range(N):
    A[i] = list(map(lambda x: int(x)-1, input().split()))

days = 0
games_amount = 0
for i in range(N*(N-1)//2):
    games = 0
    not_played = set(range(N))
    for j in range(N):
        if len(A[j]) == 0 or j not in not_played or A[j][0] not in not_played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            not_played.remove(t1)
            not_played.remove(A[t1].pop(0))
            games += 1
            games_amount += 1
            if games_amount == N*(N-1)//2:
                print(days+1)
                exit(0)
        if games*2 >= N:
            break
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1

### FIXED CODE ###

import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)
### BUGGY CODE ###

def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = list(map(lambda x: int(x), inputs[1:]))

    SSSS = 1000000007

    patterns = [1]
    for step in range(1, N + 1):
        if step in broke_steps:
            ap = 0
        elif step == 1:
            ap = 1
        else:
            ap = (patterns[step - 1] + patterns[step - 2]) % SSSS
        patterns.append(ap)

    return patterns[-1]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)


### FIXED CODE ###

def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = {}
    for b in map(lambda x: int(x), inputs[1:]):
        broke_steps[b] = True

    SSSS = 1000000007

    patterns = [1]
    for step in range(1, N + 1):
        if step in broke_steps:
            ap = 0
        elif step == 1:
            ap = 1
        else:
            ap = (patterns[step - 1] + patterns[step - 2]) % SSSS
        patterns.append(ap)

    return patterns[-1]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)
### BUGGY CODE ###

h,w = map(int, input().split( ))
a = []
b = []
for i in range(h):
    ai = list(map(int, input().split( )))
    a.append(ai)
for i in range(h):
    bi = list(map(int, input().split( )))
    for j in range(w):
        a[i][j]-=bi[j]
        a[i][j] = abs(a[i][j])

dp = [[[0]*16000 for j in range(w)] for i in range(h)]
dp[0][0][a[0][0]] = 1


for j in range(1,w):
    for k in range(13000):
        dp[0][j][k] += dp[0][j-1][abs(k-a[0][j])]##aのindexは-1不要
        dp[0][j][k] += dp[0][j-1][k+a[0][j]]

for i in range(1,h):
    for j in range(w):
        for k in range(13000):
            dp[i][j][k] += dp[i-1][j][abs(k-a[i][j])]
            dp[i][j][k] += dp[i-1][j][k+a[i][j]]
            if j:
                dp[i][j][k] += dp[i][j-1][abs(k-a[i][j])]
                dp[i][j][k] += dp[i][j-1][k+a[i][j]]
ans = -1
for k in range(13000):
    if dp[h-1][w-1][k]>0:
        ans = k
        break
print(ans)





### FIXED CODE ###


h,w = map(int, input().split( ))
a = []
for i in range(h):
    ai = list(map(int, input().split( )))
    a.append(ai)
for i in range(h):
    bi = list(map(int, input().split( )))
    for j in range(w):
        a[i][j]-=bi[j]
        a[i][j] = abs(a[i][j])
###差のmaxまでをlistで確保する代わりに可能な値をsetで保持
###値が小さいのでsetからbitで保持に変更
dp = [[0 for j in range(w)] for i in range(h)]
a2 = [a[i][j] for i in range(h) for j in range(w)]
mxa = max(a2)
###中心を取る
###間違えやすいし最大値決め打ちか
tmp=1<<mxa*(h+w)+10

dp[0][0]|=tmp<<a[0][0]
dp[0][0]|=tmp>>a[0][0]

for j in range(1,w):
    dp[0][j]=dp[0][j-1]<<a[0][j]
    dp[0][j]|=dp[0][j-1]>>a[0][j]

for i in range(1,h):
    for j in range(w):###ループ一つ抜けてるわw
        dp[i][j]=dp[i-1][j]<<a[i][j]
        dp[i][j]|=dp[i-1][j]>>a[i][j]
        if j:
            dp[i][j]|=dp[i][j-1]<<a[i][j]
            dp[i][j]|=dp[i][j-1]>>a[i][j]

tmp1 = dp[h-1][w-1]

tmp1>>=mxa*(h+w)+10

###mxa=0でrange(0)になる式だと答えが出ない
for k in range(mxa*(h+w)+10):
    if tmp1&1:
        print(k)
        exit()
    tmp1>>=1
### BUGGY CODE ###

n = int(input())
t = []
for i in range(n-1):
    t.append(list(map(int, input().split())))
ans = []
for i in range(n-1):
    tmp = t[i]
    ans.append(tmp[0]+tmp[1])
    for j in range(i):
        if ans[j] > tmp[1]:
            tmp_ans = tmp[1]
            while True:
                tmp_ans += tmp[2]
                if ans[j] <= tmp_ans:
                    ans[j] = tmp_ans
                    break
        else:
            ans[j] = tmp[1]
        ans[j] += tmp[0]
ans.append(0)
for a in ans:
    print(a)


### FIXED CODE ###

n = int(input())
t = []
ans = []
for i in range(n-1):
    t.append(list(map(int, input().split())))
    tmp = t[i]
    ans.append(tmp[0]+tmp[1])
    for j in range(i):
        if ans[j] > tmp[1]:
            if ans[j] % tmp[2] != 0:
                ans[j] = ans[j] + tmp[2] - (ans[j] % tmp[2])
        else:
            ans[j] = tmp[1]
        ans[j] += tmp[0]
ans.append(0)
for a in ans:
    print(a)
### BUGGY CODE ###

import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=[0]*n
l=deque()
l.append(0)
while l:
    x=l.pop()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)


### FIXED CODE ###

import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=deque([0]*n)
l=deque()
l.append(0)
while l:
    x=l.popleft()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)
### BUGGY CODE ###

num = int(input())

words = []
for _ in range(num):
    words.append(input())

d = {}
for word in words:
    if word in d:
        d[word] += 1
    else:
        d[word] =1

max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()

for key in max_k_list:
    print(key)

### FIXED CODE ###

import numpy as np

num = int(input())

words = []
for _ in range(num):
    words.append(input())

words = tuple(words)

d = {}
for word in words:
    if word in d:
        d[word] += 1
    else:
        d[word] =1


# keyをndarrayで取得
keys = np.array([a[0] for a in d.items()])

# valueをndarrayで取得
values = np.array([a[1] for a in d.items()])

# valueがmaxであるkeyを探してくる
keys_of_max_val = keys[values == values.max()]

keys_of_max_val.sort()

print('\n'.join(keys_of_max_val))
### BUGGY CODE ###

n, m = map(int, input().split())
ac = set()
pn = 0
l = []
for i in range(m):
  p, s = map(str, input().split())
  if s == 'AC':
    ac.add(p)
  l.append([p, s])


for a in ac:
  for p in l:
    if p[0] == a and p[1] == 'WA':
      pn += 1
    elif p[0] == a and p[1] == 'AC':
      break
print(len(list(ac)), pn)

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
n, m = map(int, input().split())
ac = set()
for i in range(m):
  p, s = map(str, input().split())
  if s == 'AC':
    ac.add(p)
  elif s == 'WA' and p not in ac:
    d[p] += 1
for e in d.keys():
  if e not in ac:
    d[e] = 0
pn = d.values()
print(len(list(ac)), sum(pn))
### BUGGY CODE ###

N,K=map(int,input().split())
from collections import defaultdict
data=defaultdict(int)
for n in range(N):
    a,b=map(int,input().split())
    data[a]+=b
now=0
for i in range(len(data)):
    idx=min(data.keys())
    now+=data[idx]
    if now>=K:
        print(idx)
        break
    data.pop(idx)

### FIXED CODE ###

N,K=map(int,input().split())
from collections import defaultdict
data=[]
for n in range(N):
    data.append(tuple(map(int,input().split())))
data.sort(key=lambda x:x[0])
now=0
for i in range(len(data)):
    now+=data[i][1]
    if now>=K:
        print(data[i][0])
        break
### BUGGY CODE ###

import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint16)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        width = 0
        for w in range(W):
            total += h_chocos[:, w]
            width += 1
            if not np.all(total <= K):
                if width == 1:
                    n_cut = float("inf")
                    break
                n_cut += 1
                width += 1
                if n_cut >= ans:
                    break
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


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

import sys
inputs = sys.stdin.readlines()

n, k = map(int, inputs[0].split())
P = list(map(int, inputs[1].split()))
EP = [0.5*p + 0.5 for p in P]

print(max(sum(EP[i:i+k]) for i in range(n-k+1)))

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()

n, k = map(int, inputs[0].split())
P = list(map(int, inputs[1].split()))
EP = [0.5*p + 0.5 for p in P]

buffer = sum(EP[:k])
Q = [buffer]
for i in range(k, n):
    buffer += EP[i] - EP[i-k]
    Q.append(buffer)
print(max(Q))
### BUGGY CODE ###

# -*- coding:utf-8 -*-

n, y = map(int, input().split())
a = 10000
b = 5000
c = 1000
list = []
for i in range(n+1):
        for j in range((n+1)-i):
                for k in range((n+1)-(i+j)):
                        total = a*i + b*j + c*k
                        if total == y:
                                if (i+j+k) == n:
                                        new_list = [i, j, k]
                                        list.append(new_list)
                                        print("{} {} {}".format(i, j, k))
                                        exit()
if not list:
        print("-1 -1 -1")

### FIXED CODE ###

# -*- coding:utf-8 -*-

n, y = map(int, input().split())
a = 10000
b = 5000
c = 1000
list = []
for i in range(n+1):
        for j in range((n+1)-i):
                #for k in range((n+1)-(i+j)):
                        total = a*i + b*j + c*(n-(i+j))
                        if total == y:
                                new_list = [i, j, (n-(i+j))]
                                list.append(new_list)
                                print("{} {} {}".format(i, j, (n-(i+j))))
                                exit()
if not list:
        print("-1 -1 -1")