Harryxun/stf_run huggingface dataset:
import collections
from math import factorial

N =int(input())
cnts = [frozenset(collections.Counter(list(input())).items()) for _ in range(N)]
xs = collections.Counter(cnts)
ans = 0
for _,v in xs.items():
    if v>=1:
        a = factorial(v) // (2*factorial(v - 2))
        ans +=a
print(ans)

### FIXED CODE ###

import collections
from math import factorial

N =int(input())
cnts = [frozenset(collections.Counter(list(input())).items()) for _ in range(N)]
xs = collections.Counter(cnts)
ans = 0
for _,v in xs.items():
    if v>1:
        a = factorial(v) // (2*factorial(v - 2))
        ans +=a
print(ans)
a = int(input())
b = int(input())
print((a-1)*(b-1))

### FIXED CODE ###

a, b = map(int,input().split())
print((a-1)*(b-1))
N=int(input())
A=list(map(int,input().split()))
p=1000000007


R=[0]
G=[0]
B=[0]

#print(A)
ans=1
for i in range(N):
    if A[i]==R[-1]:
        tmp+=1
    if A[i]==G[-1]:
        tmp+=1
    if A[i]==B[-1]:
        tmp+=1
    ans = (ans*tmp)%p

    if A[i]==R[-1]:
        R.append(R[-1]+1)
        G.append(G[-1])
        B.append(B[-1])
    elif A[i]==G[-1]:
        R.append(R[-1])
        G.append(G[-1]+1)
        B.append(B[-1])
    else:
        R.append(R[-1])
        G.append(G[-1])
        B.append(B[-1]+1)
    tmp=0
    
#print(R)
#print(G)
#print(B)
print(ans)

### FIXED CODE ###

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


R=[0]
G=[0]
B=[0]

#print(A)
ans=1
for i in range(N):
    tmp=0
    if A[i]==R[-1]:
        tmp+=1
    if A[i]==G[-1]:
        tmp+=1
    if A[i]==B[-1]:
        tmp+=1
    ans = (ans*tmp)%p

    if A[i]==R[-1]:
        R.append(R[-1]+1)
        G.append(G[-1])
        B.append(B[-1])
    elif A[i]==G[-1]:
        R.append(R[-1])
        G.append(G[-1]+1)
        B.append(B[-1])
    else:
        R.append(R[-1])
        G.append(G[-1])
        B.append(B[-1]+1)
    
#print(R)
#print(G)
#print(B)
print(ans)
N = int(input())
K = int(input())

if K == 1:
    N = str(N)
    ans = (len(N)-1) * (len(N)-2) * 9
    ans += int(N[0])
    print(ans)
    # N = str(N)
    # ans = 9*(len(N)-1)+int(N[0])
    # print(ans)
elif K == 2:
    N = str(N)
    # 最上位を避けた
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位ともう一つ
    ans += (int(N[0])-1) * (len(N)-1) * 9
    # 最上位の桁のみを選ぶ場合
    ans += 1 * int(N[1])
    # 最上位+何か
    ans += 1 * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    # 最上位を避けた選び方
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他
    ans += int(N[0]) * int(N[1]) * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)


### FIXED CODE ###

N = str(input())
K = int(input())
# dp[i][j][k] :=  i桁目まで決めたとき、非ゼロの個数がj個で、
# k->0: そこまでの桁はNと完全一致, k->1: そこまでの桁ですでにN未満であることが確定
# しているときのパターン数
# kは0or1の二通り, jは0~KのK+1通り, iは0~NのN+1通り
dp = [[[0]*2 for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
    x = int(N[i])  # Nは文字列であることに注意
    for j in range(K):
        dp[i+1][j+1][1] += dp[i][j][1]*9  # すでにN未満が確定している世界線で、jの数を増やすから9倍される
        dp[i+1][j][1] += dp[i][j][1]  # すでにN未満が確定している世界線で、jの数は変えない
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]  # 新しい桁に0を埋め込んで、N以下になる道を選んだ世界線
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)  # 新しい桁に1~(x-1)のx-1通りを埋め込んでN以下になる道を選んだ世界線
            dp[i+1][j+1][0] += dp[i][j][0]  # 新しい桁にxを埋め込んでNのままであり続ける世界線
        else:
            dp[i+1][j][0] += dp[i][j][0]  # xが0の時は、Nのままであり続ける世界線は0しか入れようがない
    dp[i+1][K][1] += dp[i][K][1]
    dp[i+1][K][x>0] += dp[i][K][0]
print(sum(dp[len(N)][K]))
def dfs_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 0 and color[v] == 0:
      dfs_v(v)
  color[u] = 2
  t += 1
  f[u] = t

def dfs():
  color = [0 for i in range(n)]
  t = 0
  for u in range(n):
    dfs_v(u)
  for u in range(n):
    print u+1, d[u], f[u]

n = input()

d = [0 for i in range(n)]
f = [0 for i in range(n)]
M = [0 for i in range(n)]0 for j in range(n)]

for i in range(n):
  u, k = map(int, raw_input().split())
  for j in range(k):
   v = input()
   M[u-1][v-1] = 1

dfs()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
data = input()
count_one = 0
for i in len(data):
  num = int(data[i])
  if (num == 1):
    count_one += 1
print(count_one)


### FIXED CODE ###

data = input()
count_one = 0
for i in range(len(data)):
  num = int(data[i])
  if (num == 1):
    count_one += 1
print(count_one)
lists=[]
lists.append(s)
for i in range(2,1000000):
    print("A",i)
    if lists[-1]%2==0:
        tmp=int(lists[-1]/2)
        lists.append(tmp)
        if lists.count(tmp)==2:
            print(i)
            exit()
    else:
        tmp=(3*lists[-1])+1
        lists.append(tmp)
        if lists.count(tmp)==2:
            print(i)
            exit()

### FIXED CODE ###

#116 B
s =int(input())
lists=[]
lists.append(s)
for i in range(2,1000001):
    if lists[-1]%2==0:
        tmp=int(lists[-1]/2)
        lists.append(tmp)
        if lists.count(tmp)==2:
            print(i)
            exit()
    else:
        tmp=(3*lists[-1])+1
        lists.append(tmp)
        if lists.count(tmp)==2:
            print(i)
            exit()
n,m=map(int,input().split())
s=input()
t=input()
#l=n*m//
import fractions

def agc(n,m,s,t):
    if s[0]!=t[0]:
        return -1
    g=fractions.gcd(n,m)
    l=n*m//g
    if s[int(l//m)]!=t[int(l//n)]:
        return -1
    return  int(l)
print(agc(n,m,s,t))


### FIXED CODE ###

n,m=map(int,input().split())
s=input()
t=input()
#l=n*m//
import fractions

def agc(n,m,s,t):
    if s[0]!=t[0]:
        return -1
    g=fractions.gcd(n,m)
    if g==1:
        return  n*m
    l=n*m//g
    i=1
    while l*i<m*n:
        if s[int(l*i//m)]!=t[int(l*i//n)]:
            return -1
        i+=1
    return  int(l)
print(agc(n,m,s,t))
import math
N = int(input())
ps = []
minx = float('inf')
mini = None
for i in range(N):
  x, y = map(int, input().split())
  if x < minx:
    minx = x
    mini = i
  ps.append((x, y))

if len(ps) == 2:
  print(0.5)
  print(0.5)
  exit()

# 2点の2等分線の単位ベクトルを返す
# i -> j に対して右方向
def divvector(xi, yi, xj, yj):
  if xi == xj:
    if yj > yi: return (1, 0)
    else: return (-1, 0)
  elif yi == yj:
    if xj > xi: return (0, -1)
    else: return (0, 1)

  a = (yi - yj) / (xi - xj) # 傾き
  a = - (1/a) # 垂直
  x = math.sqrt(1/(1+a**2))
  y = math.sqrt((a**2)/(1+a**2))
  if xj > xi:
    if yj > yi: return (x, -y)
    else: return (-x, -y)
  else:
    if yj > yi: return (x, y)
    else: return (-x, y)

# p1 -> p0 -> p2 が時計回りかどうか
def clockwise(x0, y0, x1, y1, x2, y2):
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) <= 0

# 反時計回りに、凸包を求める
first = 0
now = mini
convexs = [now]
divvecs = { now: [] }
end = False
while not end:
  for j in range(N):
    if j == now: continue
    for k in range(N):
      if k == now or k == j: continue
      if not clockwise(ps[j][0], ps[j][1], ps[now][0], ps[now][1], ps[k][0], ps[k][1]):
        break
    else:
      convexs.append(j)
      divv = divvector(ps[now][0], ps[now][1], ps[j][0], ps[j][1])
      divvecs[now].append(divv)
      if j not in divvecs:
        divvecs[j] = []
      divvecs[j].append(divv)
      now = j
      if now == first:
        end = True
      break

# 凸包を構成する各頂点について、
# 隣の頂点との二等分線のなす角を360度で割ったものが確率
# 凸包を構成しない点については、確率はほぼ0
for i in range(N):
  if i not in convexs:
    print(0)
    continue
  v1, v2 = divvecs[i]
  # すでに単位ベクトルになっているので、cos = 内積
  cos = v1[0]*v2[0] + v1[1]*v2[1]
  print(math.acos(cos) / (2*math.pi))

### FIXED CODE ###

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

# i -> j のベクトル
def vec(pi, pj):
  return (pj[0] - pi[0], pj[1] - pi[1])
# i -> j 向きの外積
def det(vi, vj):
  return vi[0] * vj[1] - vi[1] * vj[0]

# 凸包を求める
cvx = []
for i in list(range(N)) + list(range(N-1))[::-1]:
  while len(cvx) >= 2 and det(vec(ps[cvx[-2]], ps[cvx[-1]]), vec(ps[cvx[-1]], ps
[i])) < 0:
    cvx.pop()
  cvx.append(i)

# 凸包の各頂点について、頂点から出る2辺のなす角を計算
ans = {}
pi = None
for i in cvx:
  x, y, j = ps[i]
  if pi is not None:
    px, py, pj = ps[pi]
    slope = math.atan2(y-py, x-px)
    if j not in ans: ans[j] = [0, 0]
    if pj not in ans: ans[pj] = [0, 0]
    ans[j][0] = slope
    ans[pj][1] = slope
  pi = i

for i in range(N):
  if i not in ans:
    print(0)
    continue
  v1, v2 = ans[i]
  if v2 < v1:
    v2 += 2*math.pi
  print(round((v2-v1) / (2*math.pi), 8))
# D
N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
q_list = [0]*Q
for i in range(Q):
    q_list[i] = int(input())

# precompute

# res
M = (N+1)//2
S1 = [0]*M
S2 = [0]*M

s1 = 0
s2 = 0
for i in range(M):
    s1 += A_list[N-1-i]
    S1[i] = s1
    s2 += A_list[N-1-2*i]
    S2[i] = s2

# bins
bins = [0]*(M-1)
for i in range(M-1):
    bins[i] = (A_list[N - (i+2)] + A_list[N - (2*i+3)]) / 2

# function for binary search
def bisearch(q):
    
    if q > bins[0]:
        return 0
    elif q <= bins[M-2]:
        return M - 1
    
    l = 0
    r = M - 2
    while l < r - 1:
        m = (l + r) // 2
        if q > bins[m]:
            r = m
        else:
            l = m
    return l+1
    
    

# first conflict
for q in q_list:
    r = bisearch(q)
    print(S1[r]+s2-S2[r])

### FIXED CODE ###

# D
N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
q_list = [0]*Q
for i in range(Q):
    q_list[i] = int(input())

# precompute

# res
M = (N+1)//2
S1 = [0]*M
S2 = [0]*M

s1 = 0
s2 = 0
for i in range(M):
    s1 += A_list[N-1-i]
    S1[i] = s1
    s2 += A_list[N-1-2*i]
    S2[i] = s2

# bins
bins = [0]*(M-1)
for i in range(M-1):
    bins[i] = (A_list[N - (i+2)] + A_list[N - (2*i+3)]) / 2

# function for binary search
def bisearch(q):
    
    if q > bins[0]:
        return 0
    elif q <= bins[M-2]:
        return M - 1
    
    l = 0
    r = M - 2
    while l < r - 1:
        m = (l + r) // 2
        if q > bins[m]:
            r = m
        else:
            l = m
    return l+1
    
    
if N > 2:
    # first conflict
    for q in q_list:
        r = bisearch(q)
        print(S1[r]+s2-S2[r])
else:
    for q in q_list:
        print(A_list[1])
a


### FIXED CODE ###

s=input()
s=str(s)
n=len(s)-2
n=str(n)
print (s[0]+n+s[-1])
import sys
sys.setrecursionlimit(10000)
 
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

def search(s,k, lis_p, lis_c, lis):
    if len(lis) >= k:
        return lis
    s = lis_p[s - 1]
    lis.append(lis_c[s - 1])
    return search(s, k, lis_p, lis_c, lis)

ans = -10**10
for i in range(n):
    l = search(i+1, k, p, c, [])
    d = max([sum(l[:j+1]) for j in range(len(l))])
    if d> ans:
        ans = d
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
C = list(map(int, input().split()))
 
ans = -(10 ** 18)
 
for si in range(N):
    x = si
    loop = []
    total = 0
    while 1:
        x = P[x]
        loop.append(C[x])
        total += C[x]
        if x == si:
            break
    T = len(loop)  # 周期の大きさ
    tmp = 0
    for i in range(T):
        tmp += loop[i]
        if K < i + 1:
            break
        now = tmp
        if total > 0:  # loopの和が正ならloopを回した方がお得
            loop_times = (K - (i + 1)) // T  # 何周できるか
            now += total * loop_times
        ans = max(ans, now)
 
print(ans)
n,k=map(int,input().split())
S=input()
O=[]
E=[]
flag=0
if n==1:
	print(0)
else:
	c=0
	for i in range(n-1):
		if S[i+1]==S[i]:
			c+=1
		else:
			if flag==0:
				O.append(c)
				c=0
				flag=1
			else:
				E.append(c)
				c=0
				flag=0
	if flag==0:
		O.append(c)
	else:
		E.append(c)
	Osum=sum(O)
	Esum=sum(E)		
	EC=len(E)
if flag==0:
	print(Osum+Esum+min(EC,k)*2)
else:
	print(Osum+Esum+min(2*EC-1,2*k))

### FIXED CODE ###

n,k=map(int,input().split())
S=input()
O=[]
E=[]
flag=0
if n==1:
	print(0)
else:
	c=0
	for i in range(n-1):
		if S[i+1]==S[i]:
			c+=1
		else:
			if flag==0:
				O.append(c)
				c=0
				flag=1
			else:
				E.append(c)
				c=0
				flag=0
	if flag==0:
		O.append(c)
	else:
		E.append(c)
	Osum=sum(O)
	Esum=sum(E)		
	EC=len(E)
	if flag==0:
		print(Osum+Esum+min(EC,k)*2)
	else:
		print(Osum+Esum+min(2*EC-1,2*k))
from itertools import accumulate

def mi():
    return map(int, input().split())

def main():
    N, K = mi()
    A = list(mi())

    for _ in range(K):
        l = [0]*N
        for i in range(N):
            left = max(i-A[i], 0)
            right = min(i+A[i]+1, N)
            l[left] += 1
            if right < N:
                l[right] -= 1
        if A != list(accumulate(l)):
            A = accumulate(l)
        else:
            break
    print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import accumulate

def mi():
    return map(int, input().split())

def main():
    N, K = mi()
    A = list(mi())

    for _ in range(K):
        l = [0]*N
        for i in range(N):
            left = max(i-A[i], 0)
            right = min(i+A[i]+1, N)
            l[left] += 1
            if right < N:
                l[right] -= 1
        if A != list(accumulate(l)):
            A = list(accumulate(l))
        else:
            break
    print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N-1)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            try: 
                colors[edge[1]] = tmp_color
            except Exception as e:
                print(0)
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

### FIXED CODE ###

import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])
import sys
import numpy as np

while 1:
    line = sys.stdin.readline()
    if line is '':
        break
    a = list(map(float, input().split()))
    A = np.array([[a[0],a[1]],
                  [a[3],a[4]]])
    b = np.array([a[2],a[5]])
    x = np.linalg.solve(A, b)
    print(x)


### FIXED CODE ###

while 1:
    try:
        a,b,c,d,e,f = map(float, input().split())  
        y=(c*d-a*f)/(b*d-a*e)
        x=(c-b*y)/a
        print("{0:.3f} {1:.3f}".format(x,y))
    except:
        break
n, y = map(int,raw_input().split())
y/=1000

h = {0:10, 1:5, 2:1}

def dfs(i, n, y, h,res ):
	if y < 0:
		return False
	if y == 0:
		if n == 0:
			return True

		return False
	if i == 2:
		if n == y:
			res[2]+= y
			return True
		return False
	res[0] +=1
	if dfs(i, n - 1, y - h[i], h,res):
		return True
	res[0] -= 1

	if dfs(i+1, n ,y, h,res):
		return True
	return False

res = [0,0,0]
if dfs(0, n, y, h, res):
	print y, res[0] * 10 + res[1]*5 + res[2]
	print res
else:
	print [-1,-1,-1]

### FIXED CODE ###

n, y = map(int,raw_input().split())
y/=1000


def g(y,n):
	for a in range(y/10 + 1):
		b,c = f(y - a * 10, n - a)
		if b != -1:
			return [a,b,c]
	return [-1,-1,-1]
def f(y,n):
	if y < 0 or n < 0:
		return [-1,-1]
	if y == 0:
		if n == 0:

			return [0,0]
		return [-1,-1]

	for b in range(y/5 + 1):
		if y - b * 5 == n - b and n - b >= 0:
			return [b,n-b]
	return [-1,-1]

print ' '.join(map(str, g(y,n)))
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
for i in range(n-3):
    exist = True
    for j in range(3):
        if not d[i+j][0] == d[i+j][1]:
            exist = False
    if exist:
        break
if exist:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

exist = False
for i in range(n-2):
    for j in range(3):
        if d[i+j][0] != d[i+j][1]:
            break
    else:
        exist = True
if exist:
    print('Yes')
else:
    print('No')
import copy
n, m = map(int, input().split())
ab_lis = []
for i in range(n):
    ab_lis.append(list(map(int, input().split())))
def rec(ab_lis, path, rew, r_day, m_ans):
    if r_day == 0:
        m_ans[0] = max(m_ans[0], rew)
        return
    for t_lis in ab_lis:
        if t_lis in path:
            continue
        elif t_lis[0] > r_day:
            m_ans[0] = max(m_ans[0], rew)
            continue
        path_c = copy.copy(path)
        path_c.append(t_lis)
        rec(ab_lis, path_c, rew + t_lis[1], r_day - 1, ans)    
m_ans = [0]
rec(ab_lis, [], 0, m, m_ans)        
print(m_ans[0])

### FIXED CODE ###

import collections
import heapq
n, m = map(int, input().split())
c = collections.defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    c[m - a].append(b)
h = []
heapq.heapify(h)    
ans = 0
for i in range(m - 1, -1, -1):
    for b in c[i]:
        heapq.heappush(h, -b)
    if len(h) >0:
        ans += -1 * heapq.heappop(h)
print(ans)
from collections import defaultdict,Counter
n = int(input())
al = list(map(int, input().split()))

c_al  = Counter(al)

if n % 2 == 0 and 0 not in c_al.values():
    print(int(2**(n/2)))
elif n % 2 != 0 and c_al[0] == 1:
    print(int(2 ** ((n // 2))))
else:
    print(0)

### FIXED CODE ###

from collections import Counter

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

c_al = Counter(al)

if n % 2 == 0:
    for k,v in c_al.items():
        if v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))

elif n % 2 != 0:
    for k, v in c_al.items():
        if k == 0:
            if v != 1:
                print(0)
                exit()
        elif v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))
maximum = float("-inf")
for i in range(K):  # gets the sum of first i numbers + last K-i numbers
    frontSum = 0
    frontList = []
    backSum = 0
    backList = []
    for o in range(i):
        frontSum += V[o]
        frontList.append(V[o])
    for o in range(len(V)-(K-i), len(V)):
        backSum += V[o]
        backList.append(V[o])
    total = frontSum + backSum
    if total > maximum:
        maximum = total
    frontList.sort()
    backList.sort()
    for p in range(2, len(frontList), 2):
        for j in range(p):
            frontList = frontList[p:]
            newFrontSum = 0
            for k in frontList:
                newFrontSum += k
            if newFrontSum > frontSum:
                frontSum = newFrontSum
    for p in range(2, len(backList), 2):
        for j in range(p):
            backList = backList[p:]
            newBackSum = 0
            for k in backList:
                newBackSum += k
            if newBackSum > backSum:
                backSum = newBackSum
    newTotal = backSum + frontSum
    if newTotal > maximum:
        maximum = newTotal
print(maximum)


### FIXED CODE ###

N, K = map(int, input().strip().split())
V = list(map(int, input().strip().split()))
H = []
maxi = 0
for i in range(min(N, K)):
    for o in range(i+2):  # error1
        ts = 0
        hand = []
        for p in range(o):
            hand.append(V[p])
        for p in range(N-(i-o)-1, N):  # error2
            hand.append(V[p])
        for values in hand:
            ts += values
        if ts > maxi:
            maxi = ts
        if len(hand) > 0:
            hand.sort()
            for j in range(K-i-1):  # error3
                if len(hand) > 0:
                    if hand[0] < 0:
                        del hand[0]
                    else:
                        break
        ts = 0
        for k in hand:
            ts += k
        if ts > maxi:
            maxi = ts
print(maxi)
n=int(input())
a=list(map(int,input().split()))

tree=[[] for _ in range(n)]
for _ in range(n-1):
    aa,bb=map(int,input().split())
    tree[aa-1].append(bb-1)
    tree[bb-1].append(aa-1)

ans=[0]*n
import bisect

#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

def lisOnTree(x,lis):
    global ans,tree,a,n
    i=bisect.bisect_left(lis, a[x])
    if i==len(lis):
        lis.append(a[x])
        flag="append"
    else:
        flag=(i,lis[i])
        lis[i]=a[x]
    #print(x,lis)
    ans[x]=len(lis)
    for item in tree[x]:
        if ans[item]==0:
            lisOnTree(item,lis)
    if flag=="append":
        lis.pop()
    else:
        lis[flag[0]]=flag[1]

lisOnTree(0,[])

for item in ans:
    print(item)


    




### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

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

tree=[[] for _ in range(n)]
for _ in range(n-1):
    aa,bb=map(int,input().split())
    tree[aa-1].append(bb-1)
    tree[bb-1].append(aa-1)

ans=[0]*n
import bisect

#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

def lisOnTree(x,lis):
    global ans,tree,a,n
    i=bisect.bisect_left(lis, a[x])
    if i==len(lis):
        lis.append(a[x])
        flag="append"
    else:
        flag=(i,lis[i])
        lis[i]=a[x]
    #print(x,lis)
    ans[x]=len(lis)
    for item in tree[x]:
        if ans[item]==0:
            lisOnTree(item,lis)
    if flag=="append":
        lis.pop()
    else:
        lis[flag[0]]=flag[1]

lisOnTree(0,[])

for item in ans:
    print(item)
list1 = list(map(int,input().split()))
list1.sort()
if list1[0] == 5 and list[1] ==7 and list[2]==7:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

list1 = list(map(int,input().split()))
list1.sort()
if list1[0]==5 and list1[1]==5 and list1[2]==7:
  print("YES")
else:
  print("NO")
H, N = map(int, input().split()) 
abl = []
for _ in range(N):
    ab = list(map(int, input().split()) )
    abl.append(ab)

dp = [10**8]*(2*H)
dp[0] = 0
for h in range(H+1):
    for ab in abl:
        a,b = ab
        dp[h+a] = min(dp[h+a], dp[h]+b)

print(min( dp[H:] ))

### FIXED CODE ###

H, N = map(int, input().split()) 
abl = []
for _ in range(N):
    ab = list(map(int, input().split()) )
    abl.append(ab)

dp = [10**8]*(2*10**4+1)
dp[0] = 0
for h in range(H+1):
    for ab in abl:
        a,b = ab
        dp[h+a] = min(dp[h+a], dp[h]+b)

print(min( dp[H:] ))