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

import collections
import copy
N,K = map(int, input().split())
V = collections.deque(map(int, input().split()))

answer = [[0]*(K+1) for _ in range(K+1)]


for i in range(1,K+1):
    for j in range(1,min(i+1,N+1)):
        opt = 0
        for k in range(j+1):
            tmp = copy.deepcopy(V)
            tmp2 = []
            for _ in range(k):
                tmp2.append(tmp.popleft())
            for _ in range(j-k):
                tmp2.append(tmp.pop())
            tmp2.sort()
            for l in range(min(i-j,j)):
                if tmp2[l] < 0:
                    tmp2[l] = 0
            S = sum(tmp2)
            if S > opt:
                opt = S
        answer[i][j] = opt
print(max(max(answer)))

### FIXED CODE ###

def main():
    import collections
    import copy
    N,K = map(int, input().split())
    V = collections.deque(map(int, input().split()))

    answer = [[0]*(K+1) for _ in range(K+1)]


    for i in range(1,K+1):
        for j in range(max(1,i//2),min(i+1,N+1)):
            opt = 0
            for k in range(j+1):
                tmp = copy.deepcopy(V)
                tmp2 = collections.deque()
                for _ in range(k):
                    tmp2.append(tmp.popleft())
                for _ in range(j-k):
                    tmp2.append(tmp.pop())
                tmp2 = list(tmp2)
                tmp2.sort()
                for l in range(min(i-j,j)):
                    if tmp2[l] < 0:
                        tmp2[l] = 0
                S = sum(tmp2)
                if S > opt:
                    opt = S
            answer[i][j] = opt
    Ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if answer[i][j] > Ans:
                Ans = answer[i][j]
    print(Ans)

main()
### BUGGY CODE ###

import collections
n = int(input())
ls = [int(input()) for i in range(n)]
ls.sort()
c = collections.Counter(ls)
p = 0
for j in range(len(c)):
    if c.most_common()[j][1] % 2 ==0:
        continue
    else:
        p += 1
print(p)

### FIXED CODE ###

import collections
n = int(input())
ls = [int(input()) for i in range(n)]
ls.sort()
c = collections.Counter(ls)
d = list(c)
p = 0
for j in range(len(c)):
    if c[d[j]] % 2 ==0:
        continue
    else:
        p += 1
print(p)
### BUGGY CODE ###

# M日後に最大の値
N, M = map(int, input().split())
# [0] -> 日数, [1] -> お金
Data = [list(map(int, input().split())) for _ in range(N)]

temp = []
ans = 0
for i in range(1, M+1):
    N = len(Data)

    for j in range(N-1, -1, -1):  #range(N)
        if (Data[j][0] <= i):
            iranai = Data.pop(j)
            temp.append(iranai[1])

    if len(temp) != 0:
        ans += max(temp)
        temp.remove(max(temp))
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
N, M = map(int, input().split())

Data = [list(map(int, input().split())) for _ in range(N)]
Data.sort(reverse = True)

heap = [0] * M
ans = 0
for i in range(1, M+1):
    N = len(Data)
    for j in range(N-1, -1, -1):
        if Data[j][0] > i:
            break
        if (Data[j][0] <= i):
            heappush(heap, -(Data.pop(j)[1]))

    ans += -(heappop(heap))

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

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))

    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = dist[b-1][a-1] = c
    for i in range(N):
        dist[i][i] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

s=input()
l=len(s)
cnts=[0]*2019
cnts[0]=1
mod=2019
ans=0
for i in range(1,l+1):
    num = int(s[-i:])%mod
    cnts[num]+=1

for i in range(2018):
    ans+= cnts[i]*(cnts[i]-1)//2

print(ans)

### FIXED CODE ###

s= input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    num = sum_of_digits % 2019
    d *= 10
    d %=2019
    cnts[num] += 1
 
ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)
### BUGGY CODE ###

A, B, N = map(int, input().split())

if N < B:
    print((A*N)//B)
    exit()

qa, ra = divmod(A, B)
ans = 0
rx = 0

for x in range(N+1):
    rx = max(rx, x%B)
    if rx == B-1:
        break

print(qa*rx + (ra*rx)//B)


### FIXED CODE ###

A, B, N = map(int, input().split())

if N < B:
    print((A*N)//B)
else:
    qa, ra = divmod(A, B)
    rx = B-1
    print(qa*rx + (ra*rx)//B)
### BUGGY CODE ###

import sys
N=int(input())
s = list(map(int, input().split()))
ans =1
for i in s:
    ans*=i
    
if ans>1e18:
    print(-1)
    sys.exit(0)

print(ans)


### FIXED CODE ###

import sys
N=int(input())
s = list(map(int, input().split()))
ans =1
for i in s:
    if i==0:
        print(0)
        sys.exit()
    
for i in s:
    ans*=i
    if ans>1e18:
        print(-1)
        sys.exit()

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

def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = {i: 0 for i in range(13)}
    table2 = {i: 0 for i in range(13)}
    table1[0] = 1
    pre = [[((10 * i + j) % 13) for j in range(10)] for i in range(13)]

    for l in s:
        if l == '?':
            for i in range(13):
                q = table1[i]
                for k in pre[i]:
                    table2[k] += q % mod
        else:
            for i in range(13):
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q % mod

        table1 = table2
        table2 = {i: 0 for i in range(13)}

    print(table1[5] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[((10 * i + j) % 13) for j in range(10)] for i in range(13)]

    for l in s:
        for i in range(13):
            q = table1[i] % mod
            if q == 0:
                continue
            if l == '?':
                for k in pre[i]:
                    table2[k] += q
            else:
                k = (10 * i + int(l)) % 13
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


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

# -*- coding:utf-8 -*-
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
min = n
range_value = one_index if k > one_index else k
for i in range(range_value+1):
    left = one_index - k + i + 1
    right = len(nums[one_index+1:]) - i
    if left + right > n-1:
        break
    else:
        min_tmp = (-(-left//(k-1)))+(-(-right//(k-1)))+1
        if min > min_tmp:
            min = min_tmp
print(min)


### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
if k == len(nums):
    print(1)
else:
    print(math.ceil((n-1)/(k-1)))
### BUGGY CODE ###

X=int(input())
for B in range(-10**9,10**9):
    if type((X+B**5)**0.2)!=complex:
        if (X+B**5)**0.2==int((X+B**5)**0.2):
            print(int((X+B**5)**0.2), B)
            break

### FIXED CODE ###

X=int(input())
for B in range(-10**3,10**3):
    if type((X+B**5)**0.2)!=complex:
        if int((X+B**5)**0.2)-0.0001<=(X+B**5)**0.2<=int((X+B**5)**0.2)+0.0001:
            print(int((X+B**5)**0.2), B)
            break
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
from fractions import gcd
 
mod = 10**9+7
 
n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d *= a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
  ans %= mod
 
print(ans)


### FIXED CODE ###

from sys import stdin
input = stdin.readline
from fractions import gcd
 
mod = 10**9+7
 
n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d *= a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
 
print(ans%mod)
### BUGGY CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Asum = []
Bsum = []
a = 0
b = 0
for i in range(N):
    a += A[i]
    Asum.append(a)
for i in range(M):
    b += B[i]
    Bsum.append(b)
Asum.append(0)
Bsum.append(0)
res = 0
for i in range(-1,N):
    for j in range(-1,M):
        if Asum[i] + Bsum[j] <= K:
           res = max(res,(i+j+2))
        else:
           break
print(res)

### FIXED CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Asum = [0]
Bsum = [0]
a = 0
b = 0
for i in range(N):
    a += A[i]
    Asum.append(a)
for i in range(M):
    b += B[i]
    Bsum.append(b)
Asum.append(0)
Bsum.append(0)
res, j = 0, M
for i in range(N+1):
    if Asum[i] > K:
        break
    while Asum[i] + Bsum[j] > K:
            j -= 1
    res = max(res,i+j)
print(res)
### BUGGY CODE ###

N = int(input())
match = []

for i in range(1, int((2*N)**(1/2)+1)):
  for j in range(1, int((2*N)**(1/2)+1)):
    for k in range(1, int((2*N)**(1/2)+1)):
      matched = i**2 + j**2 + k**2 + i*j + j*k + k*i
      match.append(matched)
match.sort()

for i in range(1,N+1):
  num = 0
  while i == match[0]:
    match = match[1:]
    num += 1
  print(num)

### FIXED CODE ###

N = int(input())
num = [0 for i in range(7*N)]

for x in range(1, int(N**0.5)+1):
  for y in range(1, int(N**0.5)+1):
    for z in range(1, int(N**0.5)+1):
      f_N = x**2 + y**2 + z**2 + x*y + y*z + z*x
      num[f_N] += 1

for i in range(N):
  print(num[i+1])
### BUGGY CODE ###

N = int(input())
num = 1
flag = 0
c=list(map(int, input().split()))
for i in c:
    if i == 0:
        flag = 1
        print("0")
if flag == 0:
    for i in c:
        num *= i
    if num > 1000000000000000000:
        print("-1")
    else:
        print(num)

### FIXED CODE ###

N = int(input())
num = 1
flag = 0
c=[int(i) for i in input().split()]
for i in c:
    if i == 0:
        flag = 1
        print("0")
if flag == 0:
    for i in c:
        num *= i
        if num > 1000000000000000000:
            print("-1")
            flag =1
            break
if flag == 0:
    
    print(num)
### BUGGY CODE ###

def main():
  S = input()
  Q = int(input())
  que = [list(input().split()) for _ in range(Q)]
  judge = False
  for l in que:
    if int(l[0])==1:
      if judge:
        judge = False
      else:
        judge = True

    elif int(l[0])==2:
      f,c = int(l[1]),l[2]
      if judge:
        if f==1:
          f=2
        elif f==2:
          f=1
      if f==1:
        S=c+S
      elif f==2:
        S=S+c

  if judge:
    S=S[::-1]
  print(S)
  
main()

### FIXED CODE ###

def main():
  S = input()
  Q = int(input())
  import sys
  que = [list(sys.stdin.readline().split()) for _ in range(Q)]
  pre=''
  post=''
  judge = False
  for l in que:
    if int(l[0])==1:
      if judge:
        judge = False
      else:
        judge = True

    elif int(l[0])==2:
      f,c = int(l[1]),l[2]
      if judge:
        if f==1:
          f=2
        elif f==2:
          f=1
      if f==1:
        pre = ''.join([pre,c])
      elif f==2:
        post = ''.join([post,c])

  pre = pre[::-1]
  S = pre+S+post
  if judge:
    S=S[::-1]
  print(S)
  
main()
### BUGGY CODE ###

n,a,b,c,d,e = (int(input()) for _ in range(6))
one=n
two=0
three=0
four=0
five=0
six=0
count=0
while six!=n:
  count+=1
  if ((five==0 and count==1) or five>0) and count>=5:
    if five>=e:
      five=five-e
      six+=e
    else:
      six+=five
      five=0
  if ((four==0 and count==1) or four>0) and count>=4:
    if four>=d:
      four=four-d
      five+=d
    else:
      five+=four
      four=0
  if ((three==0 and count==1) or three>0) and count>=3:
    if three>=c:
      three=three-c
      four+=c
    else:
      four+=three
      three=0
  if ((two==0 and count==1) or two>0) and count>=2:
    if two>=b:
      two=two-b
      three+=b
    else:
      three+=two
      two=0
  if one>0:
    if one>=a:
      one=one-a
      two+=a
    else:
      two+=one
      one=0
  else:pass
print(count)


### FIXED CODE ###

n,a,b,c,d,e = (int(input()) for _ in range(6))
print(-(-n//min(a,b,c,d,e))+4)
### BUGGY CODE ###

N,K = map(int,input().split())
INF = 10**12
Data = list(map(int,input().split()))
Data.insert(0,0)
DP = [INF]*(N+1)
DP[1]=0
for i in range(2,N+1):
    for j in range(1,K+1):
        if i-j >= 1:
            diff = abs(Data[i]-Data[i-j])
            DP[i] = min(DP[i],DP[i-j]+diff)
print(DP[N])

### FIXED CODE ###

N,K = map(int,input().split())
INF = 10**12
Data = list(map(int,input().split()))
Data.insert(0,0)
DP = [INF]*(N+1)
DP[1]=0
for i in range(2,N+1):
    for j in range(1,K+1):
        if i-j >= 1:
            diff = abs(Data[i]-Data[i-j])
            DP[i] = min(DP[i],DP[i-j]+diff)
print(DP[N])
### BUGGY CODE ###

from fractions import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases += 1
    elif a * b >=0 and b != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print((ans+zero_cases-1) % MOD)


### FIXED CODE ###

n=int(input())

mod=10**9+7

#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 

def seiki(x,y):
    tmp=gcd(x,y)
    return (x//tmp,y//tmp)

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a==0 and b==0:
        zero+=1
    elif a*b>0:
        tmp=seiki(abs(a),abs(b))
        pp[tmp]+=1
    elif a==0:
        pp[(1,0)]+=1
    elif b==0:
        pm[(1,0)]+=1
        pp[(1,0)]+=0
    else:
        tmp=seiki(abs(b),abs(a))
        pm[tmp]+=1
        pp[tmp]+=0
#print(pm)
#print(pp)
result=1
for key in pp.keys():
    pp_v=pp[key]
    pm_v=pm[key]
    result*=(pow(2,pm_v,mod)+pow(2,pp_v,mod)-1)
    result%=mod

print((result-1+zero)%mod)
### BUGGY CODE ###

S = input()
n = len(S)
k = int(input())
cnt = 0
itl = sorted(list(set(S)))
ans = set([])
for w in itl:
    for i, s in enumerate(S):
        if s != w:
            continue
        else:
            for j in range(i+1, n+1):
                ans.add(S[i:j])
    cnt += len(ans)
    if cnt >= k:
        break
    else:
        ans.clear()

ans = list(ans)
ans.sort()
index = k - 1 - (cnt - len(ans))
print(ans[index])


### FIXED CODE ###

S = input()
n = len(S)
k = int(input())
cnt = 0
itl = sorted(list(set(S)))
ans = set([])
for w in itl:
    for i, s in enumerate(S):
        if s != w:
            continue
        else:
            for j in range(i+1, i+k+1):
                ans.add(S[i:j])
    cnt += len(ans)
    if cnt >= k:
        break
    else:
        ans.clear()

ans = list(ans)
ans.sort()
index = k - 1 - (cnt - len(ans))
print(ans[index])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

ans = []
n = ini()
a = inl()
count = 0
for i in range(1, n+1):
    ans.append(a.count(i))
out(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
a = inl()
ans = [0] * n
for i in a:
    ans[i-1] += 1
out(ans)
### BUGGY CODE ###

N = int(input())
A=[]
B=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
d=''
count = ''
countw = 0
for i in range(0,N):
    A.append(input())
    for j in range(0, len(B)):
        d = str(A[i].count(B[j]))
        count += d
    A[i]=int(count)
    count=''
for i in range(0,N):
    for j in range(1,N-i):
        if A[i]==A[i+j]:
            countw += 1
print(countw)


### FIXED CODE ###

N = int(input())
A=[]
count=1
ss=0
for i in range(0,N):
    A.append(list(input()))
    A[i].sort()
A.sort()
A.append('0')
for j in range(1,N+1):
    if A[j-1]==A[j]:
        count+=1
        j+=1
    else:
        ss+=count*(count-1)/2
        count = 1
        j+=1

print(int(ss))
### BUGGY CODE ###

import numpy as np 
H, N = map(int, input().split())

dp = [np.inf for _ in range(H+1)]

# min_cost = np.inf
dp[0]=0
for n in range(N):
    a,b =  map(int, input().split())
    for h in range(H):
        if dp[h]!=np.inf:
            nj = min(h+a,H)
            dp[nj] = min([dp[nj],dp[h]+b])
            # if h+a<H:
            #     dp[h+a] = np.min([dp[h+a], dp[h]+b])
            # elif dp[h]+b<min_cost:
            #     min_cost = dp[h]+b
        
print(int(dp[H]))

### FIXED CODE ###

H, N = map(int, input().split())
inf =1000100001001000
dp = [inf for _ in range(H+1)]
 
# min_cost = np.inf
dp[0]=0
for n in range(N):
    a,b =  map(int, input().split())
    for h in range(H):
        nj = min(h+a,H)
        dp[nj] = min([dp[nj],dp[h]+b])
        
print(int(dp[H]))
### BUGGY CODE ###

import sys
import math
from functools import reduce
N = str(input())
A = list(map(int, input().split()))

def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
d = 0
for i,o in enumerate(A):
    if i == N:
        break
    for l in A[i+1:]:
        if math.gcd(o,l) != 1:
            d = 1
            break
            
if d == 0:
    print('pairwise coprime')
    exit()

if gcd(*A) == 1:
    print('setwise coprime')
    exit()

print('not coprime')


### FIXED CODE ###

import sys
import math
from functools import reduce
N = str(input())
A = list(map(int, input().split()))

M = 10 ** 6
sieve = [0] * (M+1)
for a in  A:
    sieve[a] += 1

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

d = 0
for i in range(2, M+1):
    tmp = 0
    for j in range(i,M+1,i):
        tmp += sieve[j]
    if tmp > 1:
        d = 1
        break

            
if d == 0:
    print('pairwise coprime')
    exit()

if gcd(*A) == 1:
    print('setwise coprime')
    exit()

print('not coprime')
### BUGGY CODE ###

import sys
import itertools

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
S = [input().rstrip() for _ in range(N)]

S = [s for s in S if s[0] in 'MARCH']

C = list(itertools.combinations(S, 3))
#print(C)

cnt = 0
for c in C:
	#print(c)
	x, y, z = c
	if x[0] != y[0] and y[0] != z[0] and x[0] != z[0]:
		cnt += 1

print(cnt)

### FIXED CODE ###

import sys
from operator import mul
from functools import reduce

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

MARCH = 'MARCH'
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = INT()
S = [input().rstrip() for _ in range(N)]

S = [s for s in S if s[0] in MARCH]

A = [0]*5
for s in S:
	A[MARCH.index(s[0])] += 1

#print(A)

if sum(A) < 3:
	print(0)
	sys.exit()

ans = cmb(sum(A), 3)
#print(ans)

for a in A:
	if a<=1:continue
	if a>=3:
		ans -= cmb(a, 3)
	ans -= cmb(a, 2) * (sum(A)-a)

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

from collections import defaultdict

def main():

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

    adj = defaultdict(list)
    in_deg = defaultdict(int)
    for u, row in enumerate(a, 1):
        for v1, v2 in zip(row, row[1:]):
            uu1, vv1 = min(u, v1), max(u, v1)
            uu2, vv2 = min(u, v2), max(u, v2)
            match1 = uu1 + vv1 * 1000
            match2 = uu2 + vv2 * 1000
            adj[match1].append(match2)
            in_deg[match1]
            in_deg[match2] += 1

    now = [key for key, val in in_deg.items() if val == 0]
    day = 0
    while now:
        day += 1
        nxt = []
        for u in now:
            for v in adj[u]:
                in_deg[v] -= 1
                if in_deg[v] == 0:
                    nxt.append(v)

        now = nxt

    if max(in_deg.values()) > 0:
        day = -1

    print(day)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [[] for _ in range(match_sm)]
in_deg = [0] * match_sm
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [i for i, e in enumerate(in_deg) if e == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if in_deg.count(0) != match_sm:
    day = -1

print(day)
### BUGGY CODE ###

from sys import maxsize

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

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])


### FIXED CODE ###

from sys import maxsize

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

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])