Harryxun/stf_run huggingface dataset:
def lcs():
  x = raw_input()
  y = raw_input()
  x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
        z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:???
        z2[k+1] = z2[k]

  return z2[-1]

num = input()
for j in range(num):
  print lcs()

### FIXED CODE ###

def lcs():
  x = raw_input()
  y = raw_input()
  x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
        z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:
        z2[k+1] = z2[k]

  return z2[-1]

num = input()
for j in range(num):
  print lcs()
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

s = int((N - 1) / 2)
m = A[0:s+1]
M = A[s+1:][::-1]

n = N-1 if N % 2 == 1 else N
ans = [0 for _ in range(n)]

li = s
ri = s + 1

for i, (a, b) in enumerate(zip(m, M)):
    if i % 2 == 1:
        a, b = b, a
    ans[li] = a
    ans[ri] = b
    li -= 1
    ri += 1

if N % 2 == 1:
    if ans[0] < ans[-1]:
        ans = [m[-1]] + ans
    else:
        ans = ans + [m[-1]]

print(ans)

S = 0
for i, j in zip(ans[1:], ans[:-1]):
    S += abs(i - j)

print(S)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

if N % 2 == 0:
    c = N // 2
    S = -2 * sum(A[:c]) + 2 * sum(A[c:]) + A[c-1] - A[c]
else:
    c = (N-1) // 2
    tmp1 = -2 * sum(A[:c]) + 2 * sum(A[c+2:]) + A[c] + A[c+1]
    tmp2 = -2 * sum(A[:c-1]) + 2 * sum(A[c+1:]) - A[c-1] - A[c]
    S = max(tmp1, tmp2)

print(S)
N, A, B, C = [int(i) for i in input().split()]

ans = list()
l = list()

for i in range(N):
    l.append(input())


def dfs(i, a, b, c):
    if i == N:
        return True

    ss = l[i]
    if ss == 'AB':
        if a == 0 and  b == 0:
            return False
        if a > 0 and dfs(i + 1, a - 1, b + 1, c):
            ans.append('B')
            return True
        elif b > 0 and dfs(i + 1, a + 1, b - 1, c):
            ans.append('A')
            return True
        else:
            return False
    elif ss == 'AC':
        if a == 0 and  c == 0:
            return False
        if a > 0 and dfs(i + 1, a - 1, b, c + 1):
            ans.append('C')
            return True
        elif c > 0 and dfs(i + 1, a + 1, b, c - 1):
            ans.append('A')
            return True
        else:
            return False
    elif ss == 'BC':
        if b == 0 and  c == 0:
            return False
        if b > 0 and dfs(i + 1, a, b - 1, c + 1):
            ans.append('C')
            return True
        elif c > 0 and dfs(i + 1, a, b + 1, c - 1):
            ans.append('B')
            return True
        else:
            return False

dfs(0, A, B, C)

if len(ans) > 0:
    print('Yes')
    for a in ans:
        print(a)
else:
    print('No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)

N, A, B, C = [int(i) for i in input().split()]

ans = list()
l = list()

for n in range(N):
    l.append(input())

def dfs(i, a, b, c):
    if i == N:
        return True

    ss = l[i]
    if ss == 'AB':
        if a == 0 and b == 0:
            return False
        if b > 0 and dfs(i + 1, a + 1, b - 1, c):
            ans.append('A')
            return True
        if a > 0 and dfs(i + 1, a - 1, b + 1, c):
            ans.append('B')
            return True
    if ss == 'AC':
        if a == 0 and c == 0:
            return False
        if c > 0 and dfs(i + 1, a + 1, b, c - 1):
            ans.append('A')
            return True
        if a > 0 and dfs(i + 1, a - 1, b, c + 1):
            ans.append('C')
            return True
    if ss == 'BC':
        if b == 0 and c == 0:
            return False
        if c > 0 and dfs(i + 1, a, b + 1, c - 1):
            ans.append('B')
            return True
        if b > 0 and dfs(i + 1, a, b - 1, c + 1):
            ans.append('C')
            return True
    return False

dfs(0, A, B, C)

if len(ans) > 0:
    print('Yes')
    for x in reversed(ans):
        print(x)
else:
    print('No')
s = input()
t = input()
print(t+s)

### FIXED CODE ###

s, t = map(str, input().split())
print(t+s)
import sys


def dep(u, p):
    D[u] = p
    if tree[u][2] != NIL:
        dep(tree[u][2], p)
    if tree[u][1] != NIL:
        dep(tree[u][1], p+1)


def print_ans():
    for i in range(n):
        if tree[i][0] == NIL:
            typea = "root"
        elif tree[i][1] == NIL:
            typea = "leaf"
        else:
            typea = "internal node"
        child = []
        b = tree[i]
        if b[1] != NIL:
            child.append(b[1])
            b = tree[b[1]]
            while b[2] != NIL:
                child.append(b[2])
                b = tree[b[2]]
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i], typea, child))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
    for i in range(n):
        if tree[i][0] == NIL:
            r = i
            break
    dep(r, 0)
    print_ans()

### FIXED CODE ###

import sys


def dep(u, p):
    D[u] = p
    for i in tree[u][3]:
        dep(i, p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()
a, b = map(int(),  input())
c = int(b - a)
d =int( c * (c - 1) // 2 + c  -b)
print(d)

### FIXED CODE ###

a, b = map(int, input().split())
c = int(b - a)
d =int( c * (c - 1) // 2 + c  -b)
print(d)
import re

s = input()
pat = r"[ACGT]+"
atgc = re.findall(pat, s)
ress = []
for i in atgc:
    ress.append(len(i))

print(max(ress))


### FIXED CODE ###

import re

s = input()
n = len(s)
res = 0
for i in range(0, n):
    j = i
    tempres = 0
    while j < n and (s[j] == "A" or s[j] == "G" or s[j] == "C" or s[j] == "T"):
        j += 1
        tempres += 1
    res = max(res, tempres)

print(res)
N, X, M = map(int,input().split())
A = [X]
for i in range(N):
    An = A[-1]**2 % M
    if An in A:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)

### FIXED CODE ###

N, X, M = map(int,input().split())
A = [X]
As = set(A)
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in As:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
        As.add(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)
A, B = list(map(int, input().split()))
result = (A+B)/2 if A%2 == B%2 else "IMPOSSIBLE"
print(int(result))


### FIXED CODE ###

A, B = list(map(int, input().split()))
result = (A+B)//2 if (A+B)%2 == 0 else "IMPOSSIBLE"
print(result)
N=int(input())
l=list[map(int,input().split())]

if N>=2:
  for i in range(N):
    if l[i]<=l[i+1]:
      continue
    elif l[i]==l[i+1]+1:
      l[i+1]=l[i+1]+1
    else:
        print('No')
        
print('Yes

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
 
before = 0
result = 'Yes'
for i in range(len(h)):
    if i == 0:
        before = h[i] - 1
    else:
        if before < h[i]:
            before = h[i] - 1
        elif before == h[i]:
            before = h[i]
        else:
            result = 'No'
print(result)
from math import factorial
print(factorial(n) // factorial(r) // factorial(n - r))

N, M = map(int, input().split())
if N != 0 and M != 0:
  if N==1 and M==1:
    print(0)
  Ncon = factorial(N) // factorial(2) // factorial(N - 2)
  Mcon = factorial(M) // factorial(2) // factorial(M - 2)
  print(Ncon+Mcon)
if N ==0:
  print(factorial(M) // factorial(2) // factorial(M - 2))
if M == 0:
  print(factorial(N) // factorial(2) // factorial(N - 2))

### FIXED CODE ###

from math import factorial
 
N, M = map(int, input().split())
if N != 0 and M != 0 and N != 1 and M != 1:
  Ncon = factorial(N) // factorial(2) // factorial(N - 2)
  Mcon = factorial(M) // factorial(2) // factorial(M - 2)
  print(Ncon+Mcon)
if N ==0 or N == 1:
  if M!=1:
    print(factorial(M) // factorial(2) // factorial(M - 2))
if M == 0 or M==1:
  if N!=1:
    print(factorial(N) // factorial(2) // factorial(N - 2))
if N==1 and M==1:
  print(0)
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
score = [0]*N
visited = [False]*N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)
  
for j in range(Q):
  p, x = map(int, input().split())
  p -= 1
  score[p] += x

def dfs(pos):
  visited[pos] = True
  for next_pos in G[pos]:
    if visited[next_pos] == True:
      continue
    score[next_pos] += score[pos]
    dfs(next_pos)
dfs(0)
score = [str(s)  for s in score]
ans = ' '.join(score)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

for j in range(Q):
  p, x = map(int, input().split())
  score[p-1] += x

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)
n=100000
p=[0]*2+[1]*(n-1)
for i in range(2,n+1):
  if p[i]:
    for j in range(i*2,n+1,i):
      p[j]=0
for i in range(1,n+1)[::-1]:
  if p[i]:
    if p[(i+1)//2]:
      continue
    p[i]=0
p[2]=0
c=[0]*n
for i in range(1,n+1):
  c[i]=c[i-1]+p[i]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(c[r]-c[l-1])

### FIXED CODE ###

n=100000
p=[0]*2+[1]*(n-1)
for i in range(2,n+1):
  if p[i]:
    for j in range(i*2,n+1,i):
      p[j]=0
for i in range(1,n+1)[::-1]:
  if p[i]:
    if p[(i+1)//2]:
      continue
    p[i]=0
p[2]=0
c=[0]*(n+1)
for i in range(1,n+1):
  c[i]=c[i-1]+p[i]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(c[r]-c[l-1])
a = raw_input().split(" ")
n = int(a[0])
m = int(a[1])
S = n*m
SUM = n * 2 + m * 2
print S + " " + SUM

### FIXED CODE ###

x = raw_input().split(" ")
 
a = int(x[0])
b = int(x[1])
 
print str(a*b) + " " + str(2*(a+b))
N,S=map(int,input().split())
A=list(map(int,input().split()))
#dp[i]{:}:iまでを使って数字k個でjを作る方法
dp=[[{}]*(S+1) for _ in range(N+1)]
dp[0][0]={0:1}
for i in range(1,N+1):
  for j in range(S):
    if j+A[i]>S:
      break()
    for k,v in dp[i-1][j].items:
      dp[i][j+A[i]][k+1]+=v

print(dp[N][K])  





### FIXED CODE ###

N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
dp=[[0]*(S+1) for _ in range(N+1)]
dp[0][0]=1

for i in range(1,N+1):
  for j in range(S+1):
    dp[i][j]+=dp[i-1][j]*2
    if j-A[i-1]>=0:
      dp[i][j]+=dp[i-1][j-A[i-1]]
    dp[i][j]%=mod
print(dp[N][S])
N = int(input())
x = list(map(int, input().split()))
 
n = len(x)
 
sum_a = 0
sum_b = 0
 
for xi in x:
  sum_a += xi * xi
  sum_b += xi
  
ans = sum_a - (sum_b*sum_b)/n
min_ans = 10**9
if ans < min_ans:
    ans = min_ans
 
print(int(ans+0.5))

### FIXED CODE ###

N, R = map(int,input().split())

if N >= 10:
  print(R)
else:
  print( R+100*(10-N) )
n=int(input())
s=list(map(int,input().split()))

print('Three' if len(list(set(s))))==3 else 'Four')

### FIXED CODE ###

n=int(input())
s=input().split()
print('Four' if 'Y' in s else 'Three')
#リスト内方表記1,
K, S = map(int, input().split())
print(len([1 for X in range(K+1) for Y in range(K+1) if 0<=S-X=Y<=K]))

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for X in range(K+1):
    for Y in range(K+1):
        if 0<=S-X-Y<=K: #X+Y+Z=S Z=S-X-Y,0<=Z<=K
            count += 1
print(count)
ciar = input().split()
W,H,x,y,r = [ciar[0],ciar[1],ciar[2],ciar[3],ciar[4]]
if (x + r) <= W and (y + r) <= H and (y - r) >= 0 and (x - r) >= 0:
    print("Yes")
else :
    print("No")

### FIXED CODE ###

ciar = input().split()
W = int(ciar[0])
H = int(ciar[1])
x = int(ciar[2])
y = int(ciar[3])
r = int(ciar[4])
if (x + r) <= W and (x - r) >= 0 :
    if (y + r) <= H and (y - r) >= 0 :
        print("Yes")
    else :
        print("No")
else :
    print("No")
D,N=map(int,input().split())
for _ in range(D):
    N *= 100
print(int(N)

### FIXED CODE ###

a,b=map(int,input().split())
print(int((100**a)*(b+b//100)))
from math import pi
r=float(input())
print("{} {}".format(r*r*pi,2*pi*r))

from math import pi

r= float(input())

print("{} {}".format(r*r*pi,2*pi*r))


### FIXED CODE ###



from math import pi

r= float(input())

print("{} {}".format(r*r*pi,2*pi*r))
a,b,c = map(int(),input().split())

if b >= a * c:
  print(c)
else:
  print(int(b//a))

### FIXED CODE ###

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

if b >= a * c:
    print(c)
else:
    print(int(b//a))
x,n=map(int,input().split())
a=list(map(int,input().split()))
if n==0:
  print(x)
else:
  ans=0
  for i in range(101):
    y=x-i
    if y not in a:
      ans=y
      break
    z=x+i
    if z not in a:
      ans=z
      break
print(ans)


### FIXED CODE ###

x,n=map(int,input().split())
a=list(map(int,input().split()))
if n==0:
  ans=x
else:
  ans=0
  for i in range(101):
    y=x-i
    if y not in a:
      ans=y
      break
    z=x+i
    if z not in a:
      ans=z
      break
print(ans)
N, M, C = map(int, raw_input().split())
B = map(int , raw_input().split())
ans = 0
for i in range(0, N):
    A = map(int , raw_input().split())
    tmp = [A[m] * B[m] for m in range(M)]

    if sum(tmp) + c > 0:
        ans+=1

print(ans)


### FIXED CODE ###

N, M, C = map(int, raw_input().split())
B = map(int , raw_input().split())
ans = 0
for i in range(0, N):
    A = map(int , raw_input().split())
    tmp = [A[m] * B[m] for m in range(M)]

    if sum(tmp) + C > 0:
        ans+=1

print(ans)
[n,m] = [int(x) for x in input().split()]
ac=[0]*(n+1)
wa=[0]*(n+1)
cnt_ac=0
cnt_wa=0
for i in range(m):
	p,s=input().split()
	p=int(p)
	if s=="AC":
		if	fac[p]==0:
			cnt_ac+=1
			cnt_wa+=wa[p]
			ac[p]=1
		
	else: 
		wa[p]+=1

print(int(cnt_ac),int(cnt_wa))

### FIXED CODE ###

[n,m] = [int(x) for x in input().split()]
ac=[0]*(n+1)
wa=[0]*(n+1)
cnt_ac=0
cnt_wa=0
for i in range(m):
	p,s=input().split()
	p=int(p)
	if s=="AC":
		if ac[p]==0:
			cnt_ac+=1
			cnt_wa+=wa[p]
			ac[p]=1
	else: 
		wa[p]+=1

print(int(cnt_ac),int(cnt_wa))
costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        arr = [ a for a in A if D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()

### FIXED CODE ###

costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        arr = [ a for a in A if  n-costs[a-1]>=0 and D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
m=2*(10**5)+1
dp=[0 for i in range(m)]
#print(dp)
for i in range(n):
    x=lis[i]
    #print(x)
    for j in range(2,((m-1)//x)+1):
        dp[x*j]=1
        #print(x*j)
#print(dp)
ans=0
c=Counter(lis)
for y in lis:
    if c[y]<=1:
        ans+=1-dp[y]
print(ans)
#print(dp)
#print(dp[2*(10**5)])  

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
from collections import defaultdict
from functools import reduce
import sys
sys.setrecursionlimit(1000000)

v = defaultdict(list)
mod = 10**9+7

N, K = map(int, input().split())
for _ in range(N-1):
    a, b = map(int, input().split())
    v[a].append(b)
    v[b].append(a)

v = dict(v)
visited = [False]*(N+1)
p = [0]*(N+1)

def dfs(pos, parent, score):
    visited[pos] = True
    p[pos] = K - score
   
    a = 1 if pos==1 else 2
    b = 0

    for i in v[pos]:
        if visited[i]:continue
        dfs(i, pos, a+b)
        b += 1

dfs(1, 0, 0)
ans = reduce(lambda x,y:(x*y)%mod, p[1:])
print(ans)

### FIXED CODE ###

from collections import defaultdict
v = defaultdict(list)
mod = 10**9+7

N, K = map(int, input().split())
for _ in range(N-1):
    a, b = map(int, input().split())
    v[a].append(b)
    v[b].append(a)

visited = [False]*(N+1)
ans = 1

q = [(1, 0, 0)]
while q:
    pos, parent, score = q.pop()
    visited[pos] = True
    ans *= (K-score)
    ans %= mod 
   
    a = 1 if pos==1 else 2
    b = 0

    for i in v[pos]:
        if visited[i]:continue
        q.append((i, pos, a+b))
        b += 1

print(ans)
from heapq import heapify, heappop

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

slice_L = [v[:i] for i in range(N + 1)]
sum_L = [0]
for vv in v:
    sum_L.append(sum_L[-1] + vv)

slice_R = [v[N - 1 - i:] for i in range(-1, N)]
sum_R = [0]
for vv in v[::-1]:
    sum_R.append(sum_R[-1] + vv)

ans = 0
for put, pick in enumerate(tuple(range(K, 0, -1)), 0):
    for left in range(pick + 1):
        m_put = put
        right = pick - left
        t = sum(slice_L[left]) + sum(slice_R[right])
        q = slice_L[left] + slice_R[right]
        heapify(q)
        while m_put > 0 and q:
            t -= heappop(q)
            m_put -= 1
        if m_put > 0:
            continue
        ans = max(ans, t)
print(ans)


### FIXED CODE ###

from heapq import heapify, heappop

N, K = map(int, input().split())
vl = list(map(int, input().split()))
vr = list(reversed(vl))
sum_L = [0]
for vv in vl:
    sum_L.append(sum_L[-1] + vv)

sum_R = [0]
for vv in vr:
    sum_R.append(sum_R[-1] + vv)

ans = 0
for pick in range(min(K, N) + 1):
    for to_remove in range(K + 1):
        if pick + to_remove > K: break
        for left in range(pick + 1):
            right = pick - left

            t = sum_L[left] + sum_R[right]

            q = vl[:left] + vr[:right]
            heapify(q)

            cnt = 0
            while cnt < to_remove and q:
                t -= heappop(q)
                cnt += 1
            ans = max(ans, t)
print(ans)
import sys
sys.setrecursionlimit(10**9)
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache.get((W,n)):
    return cache[(W,n)]
  
  else:
    if wt[n-1]<=W:
      cache[(W,n)]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      return cache[(W,n)]
    else:
      cache[(W,n)]=knapsack(W,n-1)
      return cache[(W,n)]
    

def main():
    n,w=map(int,input().split())
    wt,p=[],[]
    cache={}
    for _ in range(n):
      temp_wt,temp_pr=map(int,input().split())
      wt.append(temp_wt)
      p.append(temp_pr)
    print(knapsack(w,n))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()



### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
# coding: utf-8
a,b,c,d,e,k=map(int,input())
if e-a>k:
  print(':(')
else:
  print('Yay!')

### FIXED CODE ###

# coding: utf-8
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
if e-a>k:
  print(':(')
else:
  print('Yay!')