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

import heapq

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

for _ in range(m):
        u,v,a,b = map(int,input().split())
        gyen[u-1].append([v-1,a])
        gyen[v-1].append([u-1,a])
        gsnuuk[u-1].append([v-1,b])
        gsnuuk[v-1].append([u-1,b])

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                for i in graph[u]:
                        if dist[i[0]] > du+i[1]:
                                dist[i[0]] = du+i[1]
                                heapq.heappush(q, (dist[i[0]], i[0]))
        return dist

dist_from_start = dijkstra(gyen,s-1)
dist_from_goal = dijkstra(gsnuuk,t-1)

ans = [0 for _ in range(n)]
ans[n-1] = dist_from_start[n-1]+dist_from_goal[n-1]
for i in range(n-1):
        ans[n-2-i] = min(ans[n-1-i],dist_from_start[n-2-i]+dist_from_goal[n-2-i])
[print(inf-ans[i]) for i in range(n)]

### FIXED CODE ###

import heapq
import sys
from itertools import accumulate

n,m,s,t = map(int,next(sys.stdin).split(" "))
inf = 1000000000000000
gyen = [dict() for _ in range(n)]
gsnuk = [dict() for _ in range(n)]

for _ in range(m):
        u,v,a,b = map(int,next(sys.stdin).split(" "))
        gyen[u-1][v-1] = gyen[v-1][u-1] = a
        gsnuk[u-1][v-1] = gsnuk[v-1][u-1] = b

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                for v,d in graph[u].items():
                        if dist[v] > du+d:
                                dist[v] = du+d
                                heapq.heappush(q, (dist[v], v))
        return dist

yen = dijkstra(gyen,s-1)
snuke = dijkstra(gsnuk,t-1)

ans = list(accumulate([y+s for y,s in zip(yen,snuke)][::-1],min))
[print(inf-ans[i]) for i in range(n-1,-1,-1)]
### BUGGY CODE ###

import numpy as np

N = int(input())
n = [int(x) for x in input().split()]
n=np.array(n)

a=1
for i in range(1,N):
    if np.count_nonzero(n[:i] < n[i]) : continue
    else: a+=1   
print(a)

### FIXED CODE ###

import numpy as np

N = int(input())
n = [int(x) for x in input().split()]
n=np.array(n)

a=1
pos=0
for i in range(1,N):
    if n[pos] > n[i] :
        a+=1
        pos=i
print(a)
### BUGGY CODE ###


def resolve():
    N=int(input())
    A=list(map(int,input().split()))

    for i in range(N):
        A[i]=A[i]-i-1

    minval = 10 ** 50
    j=0
    temp = 10**50
    while True:
        val=0
        for i in A:
            val+=abs(i-j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1

    minval = 10 ** 50
    j=0
    temp = 10**50
    while True:
        val=0
        for i in A:
            val+=abs(i+j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1
    print(minval)
resolve()

### FIXED CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
import numpy as np
#import statistics
#import sys
#sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    A=np.array(list(map(int,input().split())))

    for i in range(N):
        A[i]-=i+1

    B=abs(A-np.median(A))
    print(int(sum(B)))
resolve()
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
d=[]
for i in a:
  for j in b:
    d.append(i+j)
d.sort(reverse=1)
ans=[]
if len(d)>k:
  for i in d[:k]:
    for j in c:
      ans.append(i+j)
else:
  for i in d:
    for j in c:
      ans.append(i+j)
ans.sort(reverse=1)
if len(ans)>k:
  for i in ans[:k]:
    print(i)
else:
  for i in ans:
    print(i)

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
m=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      m.append(a[i]+b[j]+c[k])
m.sort(reverse=1)
for i in m[:K]:
  print(i)
### BUGGY CODE ###

import queue
def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = queue.Queue()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.put([i, j])
                counts[j][i] = 0

    while not q.empty():
        x, y = q.get()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if a[y0][x0] == '#':
                    continue
                elif counts[y][x]+1 < counts[y0][x0]:
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.put([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()


### FIXED CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()
### BUGGY CODE ###

def main(n, k, p, c):
    ans = -float('inf')
    for i in range(n):
        start, count = i, 1
        val = c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]

        start = i
        if val > 0:
            a = (k//count-1)*val
            ans = max(a, ans)
            num = k%count+count
        else:
            a = 0
            num = min(k, count)

        for j in range(num):
            start = p[start]-1
            a += c[start]
            ans = max(ans, a)
    return ans

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

print(main(n, k, p, c))


### FIXED CODE ###

from numba import jit
@jit
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -10**10
    
    for i in range(n):
        start, count = i, 1
        val = c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]

        start = i
        if val > 0:
            a = (k//count-1)*val
            ans = max(a, ans)
            num = k%count+count
        else:
            a = 0
            num = min(k, count)

        for _ in range(num):
            start = p[start]-1
            a += c[start]
            ans = max(a, ans)
    print(int(ans))

main()
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

# dp1[i] := 頂点iを白にしてその先の全体を塗り分ける通り数
dp1 = [1] * N
# dp2[i] := 頂点iを黒にしてその先の全体を塗り分ける通り数
dp2 = [1] * N
def rec(u, prev):
    for v in nodes[u]:
        if v != prev:
            rec(v, u)
            # 白 <= 白+黒 の遷移
            dp1[u] *= dp1[v] + dp2[v]
            dp1[u] %= MOD
            # 黒 <= 白 の遷移 
            dp2[u] *= dp1[v]
            dp2[u] %= MOD

rec(0, -1)
ans = (dp1[0]+dp2[0]) % MOD
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

# dp1[i] := 頂点iを白にしてその先の全体を塗り分ける通り数
dp1 = [1] * N
# dp2[i] := 頂点iを黒にしてその先の全体を塗り分ける通り数
dp2 = [1] * N
def rec(u, prev):
    for v in nodes[u]:
        if v != prev:
            rec(v, u)
            # 白 <= 白+黒 の遷移
            dp1[u] *= dp1[v] + dp2[v]
            dp1[u] %= MOD
            # 黒 <= 白 の遷移 
            dp2[u] *= dp1[v]
            dp2[u] %= MOD

rec(0, -1)
ans = (dp1[0]+dp2[0]) % MOD
print(ans)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
ans = 0
for i in range(1,n+1):
    dum = math.floor(a*i/b)-(a*math.floor(i/b))
    if dum < ans:
        break
    ans = dum
print(ans)

### FIXED CODE ###

import math
a,b,n = map(int,input().split())
if b-1 <= n:
    print(math.floor((a*(b-1))/b)-(a*math.floor((b-1)/b)))
else:
    print(math.floor((a * (n)) / b) - (a * math.floor((n) / b)))
### BUGGY CODE ###

import itertools
k,s = map(int,input().split())

cnt = 0

l = itertools.product(range(0,k+1),repeat=3)

for i in l:
  if sum(i) == s:
    cnt += 1

print(cnt)

### FIXED CODE ###

import itertools
k,s = map(int,input().split())

cnt = 0

for i in range(0,k+1):
  for j in range(0,k+1):
    z = s - i -j
    if z >= 0 and z <= k:
      cnt += 1

print(cnt)
### BUGGY CODE ###

S=list(input())
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
flag=0
ans=0
for i in range(1,len(S)+1):
    if S[-i]=="?":
        for j in range(10):
            a=(j*10**(i-1))%13
            for k in range(13):
                dp[i][(k+a)%13]+=dp[i-1][k]
    else:
        a=int(S[-i])
        a=(a*10**(i-1))%13
        for k in range(13):
            dp[i][(k+a)%13]+=dp[i-1][k]
print(dp[len(S)][5]%MOD)

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]+=dp[i][k]%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]+=dp[i][k]%MOD
print(dp[len(S)][5]%MOD)
### BUGGY CODE ###

def main():
    n = int(input())
    lis = [i for i in range(1, n + 1)]
    print(sum(lis) - len(lis))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    ans += n * (n - 1) // 2
    print(int(ans))

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

n, weightMax = map(int, input().split())
itemList = [[0 for _ in range(weightMax+1)] for _ in range(n+1)]

for i in range(n):
    w,v = list(map(int, input().split()))
    for j in reversed(range(weightMax+1)):
        if j-w >= 0:
            itemList[i+1][j] = max([itemList[i][j],itemList[i][j-w] + v])
        else:
            itemList[i+1][j] = itemList[i][j]
print(max(itemList[n]))


### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

N = int(input())

#約数を列挙する関数
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


#print(len(make_divisors(8)))

ans = 0
for C in range(1,N):
  ans += len(make_divisors(N-C))
  C += 1

print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
for A in range(1,N):
  ans += (N-1) // A
print(ans)
### BUGGY CODE ###

N,K = map( int, input().split() )
h_list = list( map( int, input().split() ) )
for i in range(150):
    h_list.append(0)
result_list = [10**10]*(N+150)
result_list[0] = 0
for i in range(N):
    for j in range(1,K+1):
        result_list[i+j] = min(result_list[i+j], result_list[i] + abs( ( h_list[i+j] - h_list[i]) ) )
print(result_list[N-1])

### FIXED CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [0]*N
for i,Hi in enumerate(H[1:],1):
    s = max(0,i-K)
    dp[i] = min( [ t + abs( Hi - hl ) for hl,t in zip(H[s:i], dp[s:i]) ] )
print(dp[N-1])
### BUGGY CODE ###

N, Y = map(int, input().split())
sum = [a*10000+b*5000+(N-a-b)*1000 for a in range(N+1) for b in range(N-a+1)]
pairs = [[a, b, N-a-b] for a in range(N+1) for b in range(N-a+1)]

if Y in sum:
    candidate = pairs[sum.index(Y)]
    print(' '.join(map(str, candidate)))
else:
    print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split())
pairs = [[a, b, N-a-b] for a in range(N+1) for b in range(N-a+1) if a*10000+b*5000+(N-a-b)*1000 == Y]

if len(pairs) != 0:
    print(" ".join(map(str, pairs[0])))
else:
    print("-1 -1 -1")
### BUGGY CODE ###

X = input().replace('ST', '')

for j in range(len(X)//2):
    X = X.replace('ST', '')
    if 'ST' not in X:
        break

print(len(X))

### FIXED CODE ###

X = input()
s = cnt = 0

for i in range(len(X)):
    if X[i] == 'S':
        s += 1
    elif s != 0:
        cnt += 2
        s -= 1

ans = len(X) - cnt
print(ans)
### BUGGY CODE ###

#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]

# params
link = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]
for u, v, c in UVW:
    u -= 1
    v -= 1
    link[u].append(v)
    link[v].append(u)
    w[u][v] = w[v][u] = c


def dfs(ans, x):
    for y in link[x]:
        if ans[y] is None:
            if w[x][y] % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 0 if ans[x] else 1
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)


def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]


# params
link = [[] for _ in range(N)]
for u, v, w in UVW:
    u -= 1
    v -= 1
    link[u].append((v, w))
    link[v].append((u, w))


def dfs(ans, x):
    for y, w in link[x]:
        if ans[y] is None:
            if w % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 0 if ans[x] else 1
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


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

X = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(X[1]):
  A[A.index(max(A))] = int(max(A)/2)
sum = 0
for a in A:
  sum+=a
print(sum)

### FIXED CODE ###

import heapq
X = list(map(int, input().split()))
# A = list(map(int, input().split()))
A = list(map(lambda x: int(x)*(-1), input().split())) # 最大値を取るために各要素を-1倍
heapq.heapify(A)

for i in range(X[1]):
  x = heapq.heappop(A) * (-1) # 最大値の取り出し
  heapq.heappush(A, int(x/2) * (-1))

ans = 0
for i in range(X[0]):
  ans -= A[i]

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

from operator import itemgetter

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC =[]

for i in range(M):
    BC.append(list(map(int,input().split())))

A.sort()
BC_sorted = sorted(BC, key=itemgetter(1), reverse=True)

for i in range(M):
    cnt = BC_sorted[i][0]
    for j in range(cnt):
        for k in range(N):
            if A[k] < BC_sorted[i][1]:
                A[k] = BC_sorted[i][1]
                break


print(sum(A))

### FIXED CODE ###

from operator import itemgetter

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC =[]

for i in range(M):
    BC.append(list(map(int,input().split())))

A.sort()
BC_sorted = sorted(BC, key=itemgetter(1), reverse=True)
# print(BC_sorted)

cur = 0

for i in range(M):
    if cur == N or A[cur]>= BC_sorted[i][1]:
        break
    for j in range(BC_sorted[i][0]):
        for k in range(cur, N):
            if A[k] < BC_sorted[i][1]:
                A[k] = BC_sorted[i][1]
                cur = k+1
                break
            elif A[k] > BC_sorted[i][1]:
                cur = k+1
                break
    # print(i, ':', A, 'cur:', cur)


print(sum(A))
### BUGGY CODE ###

def gcd(a,b,c):
    for i in range(1,10**5):
        if a%i==0 and b%i==0 and c%i==0:
            d=i
    return d
        
a=int(input())
x=0
for i in range(1,a+1):
    for j in range(1,a+1):
        for k in range(1,a+1):
            x+=gcd(i,j,k)

print(x)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

a=int(input())
x=0
for i in range(1,a+1):
    for j in range(1,a+1):
        for k in range(1,a+1):
            x+=gcd(i,j,k)

print(x)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
print(" ".join([str(A.index(i)+1) for i in range(1,N+1)]))

### FIXED CODE ###

N = int(input())
A = ["0"]*N
for a,i in zip(input().split(), range(1,N+1)):
    A[(int(a)-1)] = str(i)
print(" ".join(A))
### BUGGY CODE ###

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

# for i in range(N):
#     for j in range(N):
#         for k in range(N):
#             x = 10000 * i + 5000 * j + 1000 * k
#             if x == Y:
#                 ans = True

ans = [-1,-1,-1]
for i in range(N+1):
    for j in range(N+1):
        tmp_sum = 10000 * i + 5000 * j
        x = Y - tmp_sum
        if x >= 0:
            k = int(x//1000)
            if i + j + k == N:
                ans = [i, j, k]
        # print(i, j)


print(" ".join([str(i) for i in ans]))


### FIXED CODE ###

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

# 10000, 5000, 1000

a = -1
b = -1
c = -1

for i in range(N + 1):
    for j in range(N + 1):
        # for k in range(N + 1):
        #     cnt = i + j + k
        #     cst = 10000 * i + 5000 * j + 1000 * k
        #     if cnt == N and cst == Y:
        #         a, b, c = i, j, k
        k = N - i - j
        if k >= 0:
            cst = 10000 * i + 5000 * j + 1000 * k
            if cst == Y:
                a, b, c = i, j, k

print(a,b,c)
### BUGGY CODE ###

N = int(input())

for n in range(1,N+1):
  ans = 0
  check = False
  for x in range(1,min(n,42)):
    for y in range(x,min(n,42)):
      for z in range(y,min(n,42)):
        if (x**2 + y**2 + z**2 + x*y + y*z + z*x) == n:
          if x == y and y == x and z == x:
            ans += 1
          elif x == y  or z == x or y == z:
            ans += 3
          elif x != y and y != z and z != x:
            ans += 6
          check = True
          break
      if check:
        break
    if check:
      break
  print(ans)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10001)]

for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      v = i*i + j*j + k*k + i*j + j*k + k*i
      if v < 10001:
        ans[v] += 1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
an = 0
if K == 1:
  ans = (max(p)+1)/2
  print(ans)
else:
  r,l = 0,K -1
  while l <= N-1:
    su = sum(p[r:l+1])
    if su > an:
      an = su
    r += 1
    l += 1
  ans = an/2 + K/2

  print(ans)
  

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
an = 0
if K == 1:
  ans = (max(p)+1)/2
  print(ans)
else:
  ans = sum(p[0:K])
  an = ans
  for i in range(0,N-K):
    an = an +p[i+K] -p[i]
    ans = max(ans,an)
  num = ans/2 + K/2    
  print(num)
### BUGGY CODE ###

import copy
N = int(input())
N_ = copy.deepcopy(N)
count = 0
for K in range(2, N + 1):
    N = N_
    while K <= N:
        if N % K == 0:
            N = N / K
        else:
            N = N - K
    if N == 1:
        count += 1
print(count)

### FIXED CODE ###

# 約数を全部列挙する関数
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:  # 9の約数の場合、3*3で割る方も割られる方も同じ数のため、こういう組み合わせを除外。12の約数を求める場合3がもとまったら、4も約数。 int型で返すため, //で計算。
                divisors.append(n // i)
    return sorted(divisors)


N = int(input())

# NがKで一度も割れない場合, 最終的に1になるには、NmodK=1のため, N=aK+1と表される。そのため、K=N-1/aのため、Kは1を除く、N-1の全ての約数
count = len(divisors(N - 1)) - 1

for K in divisors(N)[1:]:
    N_ = N
    while N_ % K == 0:
        N_ = N_ // K
    N_ = N_ % K
    if N_ == 1:
        count += 1

print(count)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
res = 0
for ope in range(k+1):
    for pick in range(ope+1):
        if pick > n: continue
        for back in range(ope - pick + 1):
            for lp in range(pick+1):
                rp = pick - lp
                # print(ope,back,lp,rp)
                q = []
                for i in range(lp):
                    q.append(a[i])
                for i in range(rp):
                    q.append(a[-i-1])
                q.sort()
                q = deque(q)
                for i in range(back):
                    if not q: break
                    q.popleft()
                res = max(res, sum(q))
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
v = inpl()
m = min(n,k)
ans = 0
for a in range(m+1):
    for b in range(m+1):
        if a+b > m:
            continue
        q = deque(v)
        tmp = []
        for i in range(a):
            tmp.append(q.popleft())
        for j in range(b):
            tmp.append(q.pop())
        if k - (a + b) > 0:
            tmp.sort()
            for i in range(k-(a+b)):
                if not tmp:
                    break
                if tmp[0] < 0:
                    tmp.pop(0)
                else:
                    break
        ans = max(ans, sum(tmp))
print(ans)