CodeEff/ECCO huggingface dataset:
# Original solution
from sys import stdin
import fractions

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

point = 0

for i in li:
    lin = prime_factorize(i)
    point += lin.count(2)

print(point)

# Optimized solution
n = int(eval(input()))
li = list(map(int,input().split()))

point = 0

for i in li:
    while i%2 == 0:
        i //= 2
        point += 1

print(point)
# Original solution
#全ての要素を奇数にできれば良い
#2で何回割れるか

n=int(eval(input()))
a=[int(i) for i in input().split()]

k=0
while True:
    f=0
    for i in range(n):
        if a[i]%2==0:
            k+=1
            f=1
            a[i]=a[i]//2
    if f==0:
        break

print(k)


# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
ans=0
for i in range(n):
    while a[i]%2==0:
        ans+=1
        a[i]//=2
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
ans = 0

for i in range(n):
    while a[i]%2 == 0:
        ans += 1
        a[i] //= 2

print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
ans = 0

for i in a:
    while i%2 == 0:
        ans += 1
        i //= 2

print(ans)
# Original solution
N = int(eval(input()))
a = list(map(int, input().rstrip().split()))
even = [i for i in a if i%2 == 0]
count = 0
for i in even:
    c = 0
    for j in range(100):
        rem = i % 2
        i //= 2
        if rem == 1:
            break
        c += 1
    count += c
print(count)

# Optimized solution
N = int(eval(input()))
a = list(map(int, input().rstrip().split()))
even = [i for i in a if i%2 == 0]
count = 0
for i in even:
    c = 0
    while True:
        rem = i % 2
        i //= 2
        if rem == 1:
            break
        c += 1
    count += c
print(count)
# Original solution
N = int(eval(input()))
a = list(map(int, input().split()))
even_a = [i for i in a if i%2==0]
even_a.sort()
num = len(even_a)
count = 0

if num == 0:
    print((0))
    exit()

i = 0
while even_a[i] % 2 == 0:
    even_a[i] //= 2
    count += 1
    for j in range(i+1, num):
        even_a[j] *= 3
    if even_a[i] % 2 != 0:
        i += 1
    if i == num:
        break

print(count)

# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))
count = 0

for i in a:
    while i % 2 == 0:
        i //= 2
        count += 1

print(count)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
ans=0
for i in a:
    while True:
        if i%2!=0:
            break
        ans+=1
        i/=2
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

ans = 0
for a in A:
    while a % 2 == 0:
        if not a:
            break
        ans += 1
        a //= 2

print(ans)
# Original solution
#!/usr/bin/env python3

n = int(eval(input()))
a = list(map(int, input().split()))

def isallodd(arr):
    haseven = False
    for i in arr:
        if i%2==0:
            haseven = True
            break
    if haseven:
        return False
    else:
        return True

ans = 0 
while isallodd(a)==False:
    on = False
    for i in range(len(a)):
        if a[i]%2==1:
            a[i]*=3
        else:
            if on == False:
                a[i]//=2
                on = True
            else:
                a[i]*=3
    ans += 1 

print(ans)


# Optimized solution
#!/usr/bin/env python3

n = int(eval(input()))
a = list(map(int, input().split()))

def f(n):
    ans = 0 
    while n%2 == 0:
        n //= 2
        ans += 1
    return ans 

ans = 0 
for i in a:
    ans += f(i)

print(ans)
# Original solution
board = [[False]*1000001]*1000001
while True:
    m = int(eval(input()))
    if m == 0: break
    star = tuple(tuple(map(int, input().split())) for i in range(m))
    sx, sy = star[0]
    
    n = int(eval(input()))
    starlist = [tuple(map(int, input().split())) for i in range(n)]
    for i in range(n):
        board[starlist[i][0]][starlist[i][1]] = True
    for i in range(n):
        flag = True
        for j in range(len(star)-1):
            dx = starlist[i][0] + star[j+1][0] - sx
            dy = starlist[i][1] + star[j+1][1] - sy
            if dx < 0 or 1000000 < dx or dy < 0 or 1000000 < dy or board[dx][dy] == False:
                flag = False
                break

        if flag == True:
            print(("{} {}".format(starlist[i][0] - sx, starlist[i][1] -sy)))
            break
    

# Optimized solution
board = [[False]*1000001]*1000001
while True:
    m = int(eval(input()))
    if m == 0: break
    star = list(set(tuple(tuple(map(int, input().split())) for i in range(m))))
    sx, sy = star[0]
    
    n = int(eval(input()))
    starlist = list(set([tuple(map(int, input().split())) for i in range(n)]))
    for i in range(len(starlist)):
        board[starlist[i][0]][starlist[i][1]] = True
    for i in range(n):
        flag = True
        for j in range(len(star)-1):
            dx = starlist[i][0] + star[j+1][0] - sx
            dy = starlist[i][1] + star[j+1][1] - sy
            if dx < 0 or 1000000 < dx or dy < 0 or 1000000 < dy or board[dx][dy] == False:
                flag = False
                break

        if flag == True:
            print(("{} {}".format(starlist[i][0] - sx, starlist[i][1] -sy)))
            break
# Original solution
while True:
    try:
        a,da, b = [], [], []
        m = int(input())
        for i in range(m):
            a.append(list(map(int, input().split())))
        a = sorted(a)
        dax,day = [],[]
        for i in range(m):
            dax.append(a[i][0]-a[0][0])
            day.append(a[i][1]-a[0][1])
        n = int(input())
        for i in range(n):
            b.append(list(map(int, input().split())))
        b = sorted(b)
        bx,by = [],[]
        for i in b:
            bx.append(i[0])
            by.append(i[1])
        for i in range(n-m+1):
            for j in range(m):
                if bx.count(bx[i]+dax[j]) == 0 or by.count(by[i]+day[j]) == 0:
                    break
            else:
                print(bx[i]-a[0][0],by[i]-a[0][1])
                break
    except:
        break

# Optimized solution
while True:
    try:
        a,da, b = [], [], []
        m = int(input())
        for i in range(m):
            a.append(list(map(int, input().split())))
        a = sorted(a)
        dax = []
        for i in range(m):
            dax.append(a[i][0]-a[0][0])
        n = int(input())
        for i in range(n):
            b.append(list(map(int, input().split())))
        b = sorted(b)
        bx = []
        for i in b:
            bx.append(i[0])
        for i in range(n-m+1):
            for j in range(m):
                if bx.count(bx[i]+dax[j]) == 0:
                    break
            else:
                print(b[i][0]-a[0][0],b[i][1]-a[0][1])
                break
    except:
        break
# Original solution
while True:
    try:
        dax,bx = [],[]
        m = int(input())
        a = sorted([list(map(int, input().split())) for i in range(m)])
        for i in range(m):
            dax.append(a[i][0]-a[0][0])
        n = int(input())
        b = sorted([list(map(int, input().split())) for i in range(n)])
        for i in b:
            bx.append(i[0])
        for i in range(n-m+1):
            for j in range(m):
                if bx.count(bx[i]+dax[j]) == 0:
                    break
            else:
                print(b[i][0]-a[0][0],b[i][1]-a[0][1])
                break
    except:
        break

# Optimized solution
while True:
    try:
        m = int(input())
        a = sorted([list(map(int, input().split())) for i in range(m)])
        dax = [a[i][0]-a[0][0] for i in range(m)]
        n = int(input())
        b = sorted([list(map(int, input().split())) for i in range(n)])
        bx = [b[i][0] for i in range(n)]
        for i in range(n-m+1):
            for j in range(m):
                if bx[i]+dax[j] not in bx:
                    break
            else:
                print(b[i][0]-a[0][0],b[i][1]-a[0][1])
                break
    except:
        break
# Original solution
while 1:
    n = eval(input())
    if n == 0: break
    p = sorted([list(map(int, input().split())) for i in range(n)])
    d = [[p[i][0] - p[0][0], p[i][1] - p[0][1]] for i in range(1,n)]
    m = eval(input())
    q = sorted([list(map(int, input().split())) for i in range(m)])
    for p1 in q:
        for i in range(n-1):
            f = True
            for p2 in q:
                if p1[0] + d[i][0] == p2[0] and p1[1] + d[i][1] == p2[1]:
                    f = False
                    break
            if f: break
        else:
            print(p1[0] - p[0][0], p1[1] - p[0][1])

# Optimized solution
while 1:
    n = eval(input())
    if n == 0: break
    p = set([tuple(map(int, input().split())) for i in range(n)])
    m = eval(input())
    q = set([tuple(map(int, input().split())) for i in range(m)])
    ret = False
    for px, py in p:
        if ret: break
        for qx, qy in q:
            if ret: break
            dx = qx - px
            dy = qy - py
            for x, y in p:
                mx = x + dx
                my = y + dy
                if (mx, my) not in q:
                    break
            else:
                print(dx, dy)
                ret = True
# Original solution
while 1:
    m=int(input())
    if m==0:break
    st=[list(map(int,input().split())) for _ in range(m)]
    n=int(input())
    pi=[list(map(int,input().split())) for _ in range(n)]
    d=[[st[i][0]-st[0][0],st[i][1]-st[0][1]] for i in range(1,m)]
    for i in range(n):
        mo=[[pi[j][0]-pi[i][0],pi[j][1]-pi[i][1]] for j in range(n)]
        cnt=0
        for k in range(m-1):
            if not d[k] in mo:continue
            else:cnt+=1
        if cnt==m-1:
            print(pi[i][0]-st[0][0],pi[i][1]-st[0][1])
            break

# Optimized solution
while 1:
    m=int(input())
    if m==0:break
    st=[list(map(int,input().split())) for _ in range(m)]
    n=int(input())
    pi=[list(map(int,input().split())) for _ in range(n)]
    d=[[st[i][0]-st[0][0],st[i][1]-st[0][1]] for i in range(1,m)]
    for i in range(n):
        mo=[[pi[j][0]-pi[i][0],pi[j][1]-pi[i][1]] for j in range(n)]
        cnt=0
        cnt1=0
        for k in range(m-1):
            if not d[k] in mo:break
            else:cnt+=1
        if cnt==m-1:
            print(pi[i][0]-st[0][0],pi[i][1]-st[0][1])
            break
# Original solution
N = int(eval(input()))

def grundy(x, k):
    while x % k != 0:
        p = max(1, (x - x // k * k) // (x // k + 1))
        x = x - (x // k + 1) * p
    return x // k

g = 0

for _ in range(N):
    a, k = list(map(int, input().split()))
    g ^= grundy(a, k)

print(('Takahashi' if g != 0 else 'Aoki'))

# Optimized solution
N = int(eval(input()))
g = 0
for _ in range(N):
    x, k = list(map(int, input().split()))
    while x % k != 0:
        x = x - (x // k + 1) * max(1, (x - x // k * k) // (x // k + 1))
    g ^= x // k
print(('Takahashi' if g != 0 else 'Aoki'))
# Original solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a<2*k:return a%2^(k%2==0)
        if a%k==0:return a//k
        a-=a//k+1

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a%k==0:return a//k
        once=a//k+1
        seg=a%k
        cnt=(seg+once-1)//once
        a-=cnt*once

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")
# Original solution
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def f(ai, ki):
    if ai < ki: return 0
    elif ai % ki == 0 :return ai // ki
    d = ai // ki + 1
    return f(ai - max(ai % ki // d, 1) * d, ki)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= f(a, k)

print(("Takahashi" if ret else "Aoki"))

# Optimized solution
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def solve(n, k):
    if n % k == 0:
        return n // k
    diff = (n // k) + 1
    target = n - n % k
    if (n - target) % diff == 0:
        return solve(target, k)
    n -= -((-(n - target)) // diff) * diff
    return solve(n, k)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= solve(a, k)

print(("Takahashi" if ret else "Aoki"))
# Original solution
def main():
    import sys
    input = sys.stdin.readline

    N = int(eval(input()))
    win = 0
    for _ in range(N):
        a, k = list(map(int, input().split()))
        while True:
            if a < k:
                g = 0
                break
            elif a % k == 0:
                g = a // k
                break
            else:
                a -= (a//k) + 1
        win ^= g
    if win:
        print('Takahashi')
    else:
        print('Aoki')


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import sys
    input = sys.stdin.buffer.readline

    N = int(eval(input()))
    win = 0
    for _ in range(N):
        a, k = list(map(int, input().split()))
        while True:
            if a < k:
                g = 0
                break
            elif a % k == 0:
                g = a // k
                break
            else:
                d = (a//k) + 1
                a -= d * ((a - k * (a//k))//d)
                if a < k:
                    g = 0
                    break
                elif a % k == 0:
                    g = a // k
                    break
                else:
                    a -= d

        win ^= g
    if win:
        print('Takahashi')
    else:
        print('Aoki')


if __name__ == '__main__':
    main()
# Original solution
while True:
    a,b,c = input().split()
    if b=='?':
        break
    elif b =='+':
        d = int(a) + int(c)
    elif b=='-':
        d = int(a) - int(c)
    elif b=='*':
        d = int(a)*int(c)
    else :
        d = int(a)/int(c)
    print((int(d)))

# Optimized solution
while True:
    Input = input().split()
    a = int(Input[0])
    op = Input[1]
    b = int(Input[2])
    
    if op == '?':
        break
    
    if op == '+':
        print((a+b))
    elif op == '-':
        print((a-b))
    elif op == '*':
        print((a*b))
    else:
        print((a//b))
# Original solution
answers=[]
while True:
    iquation=[]
    iquation=input().split()
    iquation[0]=int(iquation[0])
    iquation[2]=int(iquation[2])
    if iquation[1]=='+':
        answers.append(iquation[0]+iquation[2])
    elif iquation[1]=='-':
        answers.append(iquation[0]-iquation[2])
    elif iquation[1]=='*':
        answers.append(iquation[0]*iquation[2])
    elif iquation[1]=='/':
        answers.append(int(iquation[0]/iquation[2]))
    elif iquation[1]=='?':
        break
    else:
        print('error')
for i in range(0,len(answers)):
    print((answers[i]))

# Optimized solution
while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)
    if op=="+":
        print((a+b))
    elif op=="-":
        print((a-b))
    elif op=="*":
        print((a*b))
    elif op=="/":
        print((a//b))
    elif op=="?":
        break
# Original solution
while True:
    a,op,b=input().split()
    if op=='?': break
    elif op=='+': print(( int(a) +  int(b) ))
    elif op=='-': print(( int(a) -  int(b) ))
    elif op=='*': print(( int(a) *  int(b) ))
    elif op=='/': print(( int(a) // int(b) ))

# Optimized solution
while True:
    a,op,b=input().split()
    if op=='?': break
    eval("print( int(int(a) {0} int(b)) )".format(op))
# Original solution
while 1:
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == "?":
        break
    elif op == "+":
        print((a + b))
    elif op == "-":
        print((a - b))
    elif op == "*":
        print((a * b))
    elif op == "/":
        print((int(a / b)))
        

# Optimized solution
op = ""
while op != "?":
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == "+":
        print((a + b))
    elif op == "-":
        print((a - b))
    elif op == "*":
        print((a * b))
    elif op == "/":
        print((int(a / b)))
    elif op == "?":
        break
# Original solution
h=int(eval(input()))
w=int(eval(input()))
n=int(eval(input()))

if w>=h:
 if n%w==0:
  print((n//w))
 else:
  print((n//w+1))
else:
 if n%h==0:
  print((n//h))
 else:
  print((n//h+1))

# Optimized solution
h=int(eval(input()))
w=int(eval(input()))
n=int(eval(input()))
mx=max(h,w)
if n%mx==0:
 print((n//mx))
else:
 print((n//mx+1))
# Original solution
H = int(eval(input()))
W = int(eval(input()))
N = int(eval(input()))
HW =H*W
ans =H+W
for h in range(0,H+1):
    for w in range(0,W+1):
        cntB = HW - (H-h)*(W-w)
        if cntB>=N:
            ans = min(ans, h+w)
print(ans)

# Optimized solution
h,w,n=int(eval(input())),int(eval(input())),int(eval(input()))
a=max(h,w)
print(((n+a-1)//a))
# Original solution
import math
H = int(eval(input()))
W = int(eval(input()))
N = int(eval(input()))
n = max(H,W)
print((math.ceil(N/n)))

# Optimized solution
H = int(eval(input()))
W = int(eval(input()))
N = int(eval(input()))
a = max(H,W)
n = N//a
if N%a==0:
    print(n)
else:
    print((n+1))
# Original solution
H = int(eval(input()))
W = int(eval(input()))
N = int(eval(input()))
a = max(H, W)
c = 0
ans = 0
while N > c:
    c += a
    ans += 1
print(ans)


# Optimized solution
H = int(eval(input()))
W = int(eval(input()))
N = int(eval(input()))
a = max(H, W)
print(((N+a-1)//a))
# Original solution
from math import ceil

H = int(eval(input()))
W = int(eval(input()))
N = int(eval(input()))

print((ceil(N/(max(W, H)))))


# Optimized solution
H, W, N = int(eval(input())), int(eval(input())), int(eval(input()))
print(((N+max(H, W)-1)//max(H, W)))
# Original solution
import heapq
from itertools import chain

R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
r = 0
for i in range(1, min(n, k) + 1):
    for j in range(i):
        s = 0
        h = []
        for m in chain(list(range(i - j)), list(range(n - j, n))):
            x = v[m]
            s += x
            if x < 0:
                heapq.heappush(h, x)
        j = i
        while h and j < k:
            s -= heapq.heappop(h)
            j += 1
        r = max(r, s)
print(r)


# Optimized solution
from itertools import chain
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
r = 0
for i in range(1, min(n, k) + 1):
    for j in range(i):
        r1, r2 = list(range(i - j)), list(range(n - j, n))
        s = sum(v[m] for m in chain(r1, r2))
        j = i
        for x, m in a:
            if j == k:
                break
            if m in r1 or m in r2:
                s -= x
                j += 1
        r = max(r, s)
print(r)
# Original solution
from itertools import chain
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
r = 0
for i in range(1, min(n, k) + 1):
    for j in range(i):
        r1, r2 = list(range(i - j)), list(range(n - j, n))
        s = sum(v[m] for m in chain(r1, r2))
        j = i
        for x, m in a:
            if j == k:
                break
            if m in r1 or m in r2:
                s -= x
                j += 1
        r = max(r, s)
print(r)


# Optimized solution
from itertools import chain
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
r = 0
for i in range(1, min(n, k) + 1):
    for j in range(i):
        r1, r2 = i - j, n - j
        s = sum(v[m] for m in chain(list(range(r1)), list(range(r2, n))))
        j = i
        for x, m in a:
            if j == k:
                break
            if m < r1 or m >= r2:
                s -= x
                j += 1
        r = max(r, s)
print(r)
# Original solution
from itertools import chain
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
r = 0
for i in range(1, min(n, k) + 1):
    for j in range(i):
        r1, r2 = i - j, n - j
        s = sum(v[m] for m in chain(list(range(r1)), list(range(r2, n))))
        j = i
        for x, m in a:
            if j == k:
                break
            if m < r1 or m >= r2:
                s -= x
                j += 1
        r = max(r, s)
print(r)


# Optimized solution
from itertools import chain, islice
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
ans = max(sum(v[m] for m in chain(list(range(i - j)), list(range(n - j, n)))) -
          sum(islice((x for x, m in a if m < i - j or m >= n - j), k - i))
          for i in range(1, min(n, k) + 1) for j in range(i))
print(ans)
# Original solution
from itertools import chain, islice
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
ans = max(sum(v[m] for m in chain(list(range(i - j)), list(range(n - j, n)))) -
          sum(islice((x for x, m in a if m < i - j or m >= n - j), k - i))
          for i in range(1, min(n, k) + 1) for j in range(i))
print(ans)


# Optimized solution
from itertools import islice
 
R = lambda: list(map(int, input().split()))
n, k = R()
v = list(R())
a = sorted((x, i) for i, x in enumerate(v) if x < 0)
ans = max(sum(v[:i - j] + v[n - j:]) -
          sum(islice((x for x, m in a if m < i - j or m >= n - j), k - i))
          for i in range(1, min(n, k) + 1) for j in range(i))
print(ans)