Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)

    # 辺を除かなかったときの期待値dp
    dp=[None]*n
    dp[-1]=0
    def dfs(v):
        if(dp[v] is not None): return dp[v]
        res=0
        deg=len(E[v])
        for nv in E[v]:
            res+=dfs(nv)
        dp[v]=res/deg+1
        return dp[v]

    ans=dfs(0)

    # 辺を除いたときの期待値dp
    dp1=[None]*n
    v0,w0=-1,-1
    def dfs1(v):
        if(dp1[v] is not None): return dp1[v]
        res=0
        deg=len(E[v])
        for nv in E[v]:
            if((v,nv)==(v0,w0)):
                deg-=1
            else:
                res+=dfs1(nv)
        dp1[v]=res/deg+1
        return dp1[v]

    for v0 in range(n):
        if(len(E[v0])<=1): continue
        dp1=[None]*n
        dp1[-1]=0
        w0=max((dp[w0],w0) for w0 in E[v0])[1]
        ans=min(ans,dfs1(0))

    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1;
        E[s].append(t)
    dp=[0]*n
    for v in range(n-2,-1,-1):
        res=0
        for nv in E[v]: res+=dp[nv]
        dp[v]=1+res/len(E[v])
    ans=dp[0] # 辺を消さなかった時のscore

    # 各 v に対し、削除する辺 v→u は、dp[u]が最大のもの
    for v in range(n-1):
        if(len(E[v])==1): continue
        u=max(*((dp[nv],nv) for nv in E[v]))[1]
        # vu を削除したときの期待値DPを行う
        dp2=[0]*n
        for x in range(n-2,-1,-1):
            res=0
            for nx in E[x]:
                if(x==v and nx==u): continue
                res+=dp2[nx]
            if(v!=x):
                dp2[x]=1+res/len(E[x])
            else:
                dp2[x]=1+res/(len(E[x])-1)
        ans=min(ans,dp2[0])
    print(ans)
resolve()
S=input()
T=input()
i=0
j=0
match = 0
for i in Range(len(S)-len(T)):
  count = 0
  for j in Range(Len(T)):
    if S[i+j]==T[j]:
      count=count+1
  
  if match<count:
    match=count

print(Len(T)-match)
      

### FIXED CODE ###

D,T,S = input().split()
if int(D)/int(S) > int(T):
  print('No')
else:
  print('Yes')
while True :
    a,b=input().split()
    h =int(a)
    w=int(b)
    if a==0 and b==0:
        break
    for i in range(h):
        if i %2==0:
            print(".#"*(w/2))
        elif w ==1 :
            print(#.")
        else:
            print("#."*(w-1)/2))
    print("")

### FIXED CODE ###

while True:
    a,b=input().split()
    h = int(a)
    w=int(b)
    if h==0 and w==0:
        break
    odd = "#."*300
    even= ".#"*300
    for i in range(h):
        if (i%2)==0:
            print(odd[:w])
        else:
            print(even[:w])
    print("")
N=int(input())
S=input()
count = 0
for i in range(1000):
    x= i%10
    z= i//100
    y= (i-x-(z*100))//10
    
    p=0
    for j in range(N):
        if S[j]!=str(z):
            p = p+1
        else:
            break
    if p==N:
        count = count
        break
    else:
        q=p+1
        for k in range(p+1,N):
            if S[k]!=str(y):
                q = q+1
            else:
                break
        if q == N:
            count = count
            break
        else:
            r=q+1
            for l in range(q+1,N):
                if S[l]!=str(x):
                    r = r+1
                else:
                    break
            if r == N:
                count = count
            else:
                count = count+1
 
print(count)

### FIXED CODE ###

X=int(input())
if X//100 != X//105:
  print(1)
elif X//100 == X//105 and X%105==0:
  print(1)
else:
  print(0)
# -*- coding: utf-8 -*-
# 整数の入力
a = int(raw_input())
# スペース区切りの整数の入力
a, b, c = map(int, raw_input().split())
# 出力
if 100*a+10*b+c%4 == 0:
	print "YES"

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b, c = map(int, raw_input().split())
# 出力
if (a*100+b*10+c)%4 ==0:
    print "YES"
else:
    print "NO"
N = int(input())

x_before = 0
y_before = 0
t_before = 0
ans = 'YES'

for i in range(N):
    t, x, y = map(int, input().split())
    
    #i番目とi+1番目までの距離
    distace = abs(x-x_before) + abs(y-y_before)
    
    #i番目とi+1番目までの時間
    time = abs(t-t_before)
    
    #i+1番目のtimeで行くことが可能か判定
    if((time-distace<0) or (time-distace%2!=0)):
        ans = 'NO'
        break
        
    #i+1番目のtimeで行くことが可能なら値を更新
    x_before = x
    y_before = y
    t_before = t
    
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
if(a*b%2==0):
    print('Even')
else:
    print('Odd')
# coding:utf-8

import random
r = random.randrange(1, 69)
s = raw_input(r)  # 获取输入数据字符串S
print s

s = raw_input()


if s == "Sunny":
    print "Cloudy"
elif s == "Cloudy":
    print "Rainy"
elif s == "Rainy":
    print "Sunny"

arr = ["Sunny", "Cloudy", "Rainy"]
n = arr.index(s

### FIXED CODE ###

# coding:utf-8

s = raw_input()  # 获取输入数据字符串S

if s == "Sunny":
    print "Cloudy"
elif s == "Cloudy":
    print "Rainy"
elif s == "Rainy":
    print "Sunny"
import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
    else:
      print(t)
      sys.exit()
  t+=1
      


### FIXED CODE ###

a=input()
print(a.count('1'))
#整数の入力
N = int(input())

#複数の入力
input_list = input().split( )

for i in range(N):
  if(input_list[i]%2==0):
    if((input_list[i]%3==0)or(input_list[i]%5==0)):
      counter = counter + 1
if(counter == N):
  print("APPROVED")
else:
  print("DENIED")

### FIXED CODE ###

#整数の入力
N = int(input())

#複数の入力
input_list = input().split( )

counter = 0

for i in range(N):
  if(int(input_list[i])%2==0):
    if((int(input_list[i])%3==0)or(int(input_list[i])%5==0)):
      counter = counter + 1
  else:
    counter = counter + 1
if(counter == N):
  print("APPROVED")
else:
  print("DENIED")
s = input().count(1)
print (s)

### FIXED CODE ###

print(input().count("1"))
n = int(input())

ls = [map(int(input().split())) for _ in range(n)]

sum = 0
for i in range(n-1):
  for j in range(1,n):
    sum += ((ls[i][0]-ls[j][0])**2+(ls[i][1]-ls[j][1])**2)**0.5
    
print(sum*2/n)

### FIXED CODE ###

n = int(input())

ls = [list(map(int,input().split())) for _ in range(n)]

sum = 0
for i in range(n-1):
  for j in range(i+1,n):
    sum += ((ls[i][0]-ls[j][0])**2+(ls[i][1]-ls[j][1])**2)**0.5
    
print(sum*2/n)
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

### FIXED CODE ###

import sys
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a-=1
    b-=1
    graph[a].append((b, c))
    graph[b].append((a, c))
q, k = map(int, input().split())
k -= 1
xy = []
for _ in range(q):
    x, y = map(int, input().split())
    x-=1
    y-=1
    xy.append((x, y))

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * n)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])
import math
def cal(n ,r):
    if n == r:
        return 1
    return math.factorial(n)/(math.factorial(r) * math.factorial(n-r))

def bin_search(in_list, val):
    cnt = len(in_list)
    mid = round(cnt/2)
    if cnt == 1:
        return in_list[0]
    if in_list[mid] > val:
        return bin_search(in_list[:mid], val)
    if in_list[mid] < val:
        return bin_search(in_list[mid:], val)
    if in_list[mid] == val:
        return val

n = int(input())
A = sorted(list(map(int, input().split())))

m_combo = 0
ai = 0
aj = 0

for i in range(1,n):
    a = A[i]
    val = bin_search(A[:i], round(a/2))
    upper = A[A.index(val) + 1]
    val = min(abs(val - round(a/2), upper - round(a/2))
    combo = cal(a, val)
    if combo > m_combo:
        m_combo = combo
        ai = a
        aj = val

print('{} {}'.format(ai, aj))


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))

ai = max(A)
A.remove(ai)

Asub = [abs(ai/2 -a) for a in A]
aj = A[Asub.index(min(Asub))]

print('{} {}'.format(ai, aj))
from math import sqrt

while True:
    n = int(input())
    if n == 0: break
    nums = [ x for x in range(n, 2*n+1) if x % 2 == 1 or x == 2]
    #print(nums)
    for i in range(2,int(sqrt(2*n))):
        nums = [x for x in nums if x % i != 0 or x == i]
        #print(i, nums)
    print(len(nums))

#    ans = 0
#    for i in range(n, 2*n+1):
#        for j in [x for x in range(2,i) if x * x <= i]:
#            if i % j == 0:
#                break
#        else:
#            ans += 1
#    print(ans)

### FIXED CODE ###

from math import sqrt

size = 123456
primes = [x for x in range(2, 2*size+1) if x == 2 or x % 2 == 1]
for i in range(2, int(sqrt(2*size))):
    primes = [x for x in primes if x % i != 0 or x == i]

while True:
    n = int(input())
    if n == 0: break
    nums = [x for x in primes if x > n and x <= 2*n]
    print(len(nums))
a,b = input().split()
x,y = int(input().split())
k = input()

if a == k:
  print(x-1,y)
else:
  print(x,y-1)


### FIXED CODE ###

S,T = input().split()
A,B = map(int, input().split())
U = input()

if S==U:
    A -= 1
else:
    B -= 1
print(A,B)
t,_,s=open(0).read().partition('\n')
h,w=map(int,t.split())
a,b=h//2*(w//2),h%2and w%2
d=[b,(h*w-a*4-b)//2,0,a]
for i in map(s.count,set(s)-{'\n'}):
  for j in(3,1,0):
    while d[j]and i>j:
      i-=j+1
      d[j]-=1
print('YNeos'[sum(d.values())>0::2])

### FIXED CODE ###

t,_,s=open(0).read().partition('\n')
h,w=map(int,t.split())
a=b=c=0
if h%2and w%2:
    a=h//2*(w//2)
    c=1
    b=(h*w-a*4-c)//2
elif h%2or w%2:
    a=h//2*(w//2)
    b=(h*w-a*4)//2
else:
    a=h*w//4
l=[]
for i in set(s.replace('\n','')):
    l.append(s.count(i))
for i in l:
    if i>3:
        while i>3and a:
            i-=4
            a-=1
    if i>1:
        while i>1and b:
            i-=2
            b-=1
    if i and c:
        i-=1
        c-=1
if all(not t for t in(a,b,c)):
    print('Yes')
else:
    print('No')
x=input()

if int(x[-2:])%5==0:
  if int(x[:-2])-int(x[-2:])//5>=0:
    print(1)
  else:
    print(0)
elif int(x[-2:])%4==0:
  if int(x[:-2])-int(x[-2:])//4>=0:
    print(1)
  else:
    print(0)
elif int(x[-2:])%3==0:
  if int(x[:-2])-int(x[-2:])//3>=0:
    print(1)
  else:
    print(0)
elif int(x[-2:])%2==0:
  if int(x[:-2])-int(x[-2:])//2>=0:
    print(1)
  else:
    print(0)
elif int(x[-2:])%1==0:
  if int(x[:-2])-int(x[-2:])//1>=0:
    print(1)
  else:
    print(0)
else:
  print(0)
  

### FIXED CODE ###

x=input()

if len(x)>=3:
  if int(x[-2:])%5==0:
    if int(x[:-2])-int(x[-2:])//5>=0:
      print(1)
    else:
      print(0)
  elif int(x[-2:])%4==0:
    if int(x[:-2])-int(x[-2:])//4>=0:
      print(1)
    else:
      print(0)
  elif int(x[-2:])%3==0:
    if int(x[:-2])-int(x[-2:])//3>=0:
      print(1)
    else:
      print(0)
  elif int(x[-2:])%2==0:
    if int(x[:-2])-int(x[-2:])//2>=0:
      print(1)
    else:
      print(0)
  elif int(x[-2:])%1==0:
    if int(x[:-2])-int(x[-2:])//1>=0:
      print(1)
    else:
      print(0)
  else:
    print(0)
else:
  print(0)
S = int(input())
if S < 3: return 0
MODULO = int(1e9+7)
dp = [0,0,0,1]
for i in range(4,S+1):
  x = dp[i-3] + dp[i-1]
  x %= MODULO
  dp.append(x)
print(dp[-1]

### FIXED CODE ###

S = int(input())
if S < 3:
    print(0)
else:
    MODULO = int(1e9+7)
    dp = [0,0,0,1]
    for i in range(4,S+1):
        x = dp[i-3] + dp[i-1]
        x %= MODULO
        dp.append(x)
    print(dp[-1])
x,n = map(int,input().split())
p = list(map(int,input().split()))
i = 0
if n == 0:
    print(x)
else:
    for i in range(101)
        if not x - i in p:
            print(x-i)
            break
        elif not x + i in p:
            print(x+i)
            break
        else:
            i += 1

### FIXED CODE ###

x,n = map(int,input().split())
p = list(map(int,input().split()))
i = 0
if n == 0:
    print(x)
else:
    for i in range(101):
        if not x - i in p:
            print(x-i)
            break
        elif not x + i in p:
            print(x+i)
            break
        else:
            i += 1
def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))
s = input()
t = input()

for i in range(len(t)):
  if not t[i] in s:
    print(-1)
    break
else:
  j = 0
  for i in rane(len(t)):
    j = s[j:].find(t[i])
    if j == -1:
      counter += 1
      j = s.find(t[i])
  print(counter * len(s) + j + 1)

### FIXED CODE ###

s = input()
t = input()

for i in range(len(t)):
  if not t[i] in s:
    print(-1)
    break
else:
  j = -1
  counter = 0
  for i in range(len(t)):
    if t[i] in s[j+1:]:
      j = s[j+1:].find(t[i]) + j + 1
    else:
      counter += 1
      j = s.find(t[i])
  print(counter * len(s) + j + 1)
#!/usr/bin/env python

from functools import reduce
import math

# GCD and LCM are not in math module.  They are in gmpy, but these are simple enough:

# def gcd(a,b):
#     """Compute the greatest common divisor of a and b"""
#     while b > 0:
#         a, b = b, a % b
#     return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b // math.gcd(a, b)

N = int(input())
ts = []
for _ in range(N):
  T = int(input())
  ts.append(T)

# print(reduce(lcm, ts))
ans = 1
for i in range(N):
  ans = lcm(ans, ts[i])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python

from functools import reduce
import math

# GCD and LCM are not in math module.  They are in gmpy, but these are simple enough:

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b // gcd(a, b)

N = int(input())
ts = []
for _ in range(N):
  T = int(input())
  ts.append(T)

# print(reduce(lcm, ts))
ans = 1
for i in range(N):
  ans = lcm(ans, ts[i])
print(ans)
import re
N, Q = map(int,input().split())
S = input()

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  m = re.match('AC',Si)
  print(len(m.group())

### FIXED CODE ###

b = input()
if b == 'A':
  print('T')
elif b == 'T':
  print('A')
elif b == 'C':
  print('G')
else:
  print('C')
import numpy
A, B = map(int, input().split())

C = print(A + B)
D = print(A - B)
E = print(A*B)

if C > D and C > E:
    print(C) 
elif D > C and D > E:
    print(D)
elif E > C and E > D:
    print(E)

### FIXED CODE ###

A, B = map(int, input().split())
 
C = A+B
D = A-B
E = A*B
 
LIST = [C,D,E]
 
print(max(LIST))
import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect as bi

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)

number_of_operation = [0] * O
maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    ll.append(sum([min(x, i) for i in l]) / x)

for K in range(M):
    maximum_operation[K] = N-bi.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
height, width, k = map(int, input().split())

# 範囲外を0としたいので, wを両端1つずつ多く取る
# 初期値を入れるため, hも1つ多く取る
ans = [[0] * (width + 2) for i in range(height + 1)]
start_w = 1
end_w = width
start_h = 0
ans[start_h][start_w] = 1
search_range = start_w + 1 if end_w > 1 else 1
f = [0] * (width + 2)
f[0], f[1], f[2] = 1, 1, 1


def det_unused(n, m=0):
    front = n - (start_w + 1)
    rear = end_w - (n + 1)

    if m == -1:
        front -= 1
    elif m == 1:
        rear -= 1

    ret = int(calc(front) * calc(rear))
    return ret


def calc(n):
    if n < 1:
        return 1
    return calc_f(n+2)


def calc_f(n):
    if f[n] == 0:
        f[n] = calc_f(n - 1) + calc_f(n - 2)
    return f[n]


for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        prev_ans = ans[h - 1]
        ans[h][w] = prev_ans[w] * det_unused(w) + prev_ans[w - 1] * det_unused(w, -1) + prev_ans[w + 1] * det_unused(w,
                                                                                                                     1)
    if search_range < end_w:
        search_range += 1

print(ans[height][k] % 1_000_000_007)

### FIXED CODE ###

height, width, k = map(int, input().split())

ans = [[0] * (width + 2) for i in range(height + 1)]
start_w = 1
end_w = width
start_h = 0
ans[start_h][start_w] = 1
search_range = start_w + 1 if end_w > 1 else 1
f = [0] * (width + 2)
f[0], f[1], f[2] = 1, 1, 1


def det_unused(n, m=0):
    front = n - (start_w + 1)
    rear = end_w - (n + 1)

    if m == -1:
        front -= 1
    elif m == 1:
        rear -= 1

    ret = int(calc(front) * calc(rear))
    return ret


def calc(n):
    if n < 1:
        return 1
    return calc_f(n+2)


def calc_f(n):
    if f[n] == 0:
        f[n] = calc_f(n - 1) + calc_f(n - 2)
    return f[n]


for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        prev_ans = ans[h - 1]
        ans[h][w] = prev_ans[w] * det_unused(w) + prev_ans[w - 1] * det_unused(w, -1) + prev_ans[w + 1] * det_unused(w, 1)
        ans[h][w] %= 1000000007
    if search_range < end_w:
        search_range += 1

print(ans[height][k])
primes = [0, 0] + [1]*999
for i in range(2, 32):
    if primes[i]:
        for j in range(i*i, 1001, i):
            primes[j] = 0
while True:
    n = int(input())
    if n == 0:
        break
    m = n
    while not primes[m]:
        m -= 1
    pnum = [i for i in range(m+1) if primes[i]]
    ans = 0
    for i in range(len(pnum)):
        tmp = 0
        for j in range(i, len(pnum)):
            tmp += pnum[j]
            if tmp == n:
                ans += 1
                break
            if tmp > n:
                break
    print(ans)

### FIXED CODE ###

primes = [0, 0] + [1]*9999
for i in range(2, 101):
    if primes[i]:
        for j in range(i*i, 10001, i):
            primes[j] = 0
pnums = [i for i in range(10001) if primes[i]]
while True:
    n = int(input())
    if n == 0:
        break
    m = n
    while not primes[m]:
        m -= 1
    ans = 0
    end = pnums.index(m)+1
    for i in range(end):
        tmp = 0
        for j in range(i, end):
            tmp += pnums[j]
            if tmp == n:
                ans += 1
                break
            if tmp > n:
                break
    print(ans)
n,k=map(int,input().split())

a=list(map(int,input().split()))
a_reverse=list(reversed(a))
b=sorted(a)
s=sum(a)

ans=[]

for i in range(k+1):
  if i>n:
    I=i-n
    for j in range(I): 
      ans1=s-[j]
    ans.append(ans1)
  elif i==n:
    ans.append(s)
  elif i==0:
    ans.append(0)
  else:
    for h in range(i+1):
      H=i-h
      c=[]
      for x in range(h):
        c.append(a[x])
      for y in range(H):
        c.append(a_reverse[y])
        
      c.sort()
      S=sum(c)
      for g in range(1,k-i+1):
        if g<=i:
          if c[g-1]<0:
            S-=c[g-1]

      ans.append(S)
      
print(max(ans))

### FIXED CODE ###

n,k=map(int,input().split())

a=list(map(int,input().split()))
a_reverse=list(reversed(a))
b=sorted(a)
s=sum(a)

ans=[]

for i in range(k+1):
  if i>n:
    I=i-n
    for j in range(I): 
      if j<n:
        ans1=s-b[j]
    ans.append(ans1)
  elif i==n:
    ans.append(s)
  elif i==0:
    ans.append(0)
  else:
    for h in range(i+1):
      H=i-h
      c=[]
      for x in range(h):
        c.append(a[x])
      for y in range(H):
        c.append(a_reverse[y])
        
      c.sort()
      S=sum(c)
      for g in range(1,k-i+1):
        if g<=i:
          if c[g-1]<0:
            S-=c[g-1]

      ans.append(S)
      
print(max(ans))
import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
  x=b[i]
  y=bisect.bisect_left(a,x)
  z=bisect.bisect_right(c,x)
    ans+=(n-z)*y
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
  x=b[i]
  y=bisect.bisect_left(a,x)
  z=bisect.bisect_right(c,x)
  ans+=(n-z)*y
print(ans)
anntena = []
for i in range(5):
	anntena.append(int(input())
k = int(input())
                 
if anntena[4] - anntena[0] <= k:
	print('Yey!')
else:
    print(':(')

### FIXED CODE ###

max_distance = 0
previous = int(input())
for i in range(4):
    current = int(input())
    distance = current - previous
    if distance > max_distance:
        max_distance = distance

k = int(input())

if max_distance > k:
    print(":(")
else:
    print("Yay!")
a, b, h = map(int, raw_input().split())
print (a + b) * h / 2

### FIXED CODE ###

print (input() + input()) * input() / 2
N = int(input())
d_s = list(map(int,input().split()))
d_s.sort()
print(d_s[len(d_s)]-d_s[len(d_s)-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!
N = int(input())
d_s = list(map(int,input().split()))
d_s.sort()
print(d_s[len(d_s)//2]-d_s[len(d_s)//2-1])
# S = input()
# N = int(input())
# A, B = map(int, input().split(' '))
# A = list(map(int, input().split(' ')))

A, B, C, K = map(int, input().split(' '))

card = []
a = [1]*A
b = [0]*B
c = [-1]*C

card.extend(a)
card.extend(b)
card.extend(c)


card = sorted(card, reverse=True)

print(sum(card[:K]))

### FIXED CODE ###

# S = input()
# N = int(input())
# A, B = map(int, input().split(' '))
# A = list(map(int, input().split(' ')))

A, B, C, K = map(int, input().split(' '))
result = 0

if A < K:
  result += A
  K -= A
else:
  result = K
  K -= A

if K > 0:
  if B < K:
    K -= B
  else:
    K -= B

if K > 0:
  if C < K:
    result -= C
    K -= C
  else:
    result -= K

print(result)